Discussion :

[antares56]

Bonjour à tous,

j'aimerais savoir comment on effectue une recherche dichotomique dans un tableau de String en utilisant "s1.compareto(s2)"

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
public static int rechercheDicho(String cherche , String [] t) {
            int debut = 0;
            int fin = t.length-1;
            boolean trouve = false;
 
            for(int i =0;i<t.length;i++) {
             int resul = cherche.compareTo(t[i]);
 
            int milieu = (debut + fin)/2;
            while(debut <= fin && ! trouve ) {
                if(t[milieu] == resul) {
                    trouve = true;
                }else if(resul > cherche) {
                    fin = milieu-1;
                }else {
                    debut = milieu +1;
 
                }
                milieu = (debut+fin)/2;
 
                } if(trouve) {
                    return milieu;
                }else {
                return -1;
                }
            }
            }

Mais le truc c'est que concrètement, je sais pas où placer le "compareTo" car je sais qu'il renvoi une valeur, et je crois que cette valeur dépend du placement des lettres dans l'alphabets et retourne un entier mais ça j'ai pas très bien compris exactement, en gros on va comparer la valeur que nous donne compare to et on va le comparer avec le milieu du tableau?

[Cincinnatus]

Mais le truc c'est que concrètement, je sais pas où placer le "compareTo" car je sais qu'il renvoi une valeur, et je crois que cette valeur dépend du placement des lettres dans l'alphabets et retourne un entier mais ça j'ai pas très bien compris exactement, en gros on va comparer la valeur que nous donne compare to et on va le comparer avec le milieu du tableau?

Bonjour,

Non, ça serait comparer des choux et des carottes.
compareTo retourne un résultat de comparaison (int, > 0, 0 ou < 0) selon la valeur relative des données comparées.
Alors comparer un int et un String, euh, ça donne quoi ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
if(t[milieu] == resul)

Là par exemple, quel est le sens de cette comparaison ?
D'ailleurs, dans ce code, à quoi sert 'resul' ?

Enfin, le == ne doit pas être utilisé avec les Strings, il faut utiliser le equals().

[antares56]

Merci de votre réponse !
En faites, justement je me demande avec quoi comparer "compareTo" , il faut bien le comparer avec le milieu du tableau ?

[Cincinnatus]

Merci de votre réponse !
En faites, justement je me demande avec quoi comparer "compareTo" , il faut bien le comparer avec le milieu du tableau ?

La recherche dichotomique joue sur la division de l'ensemble recherché (ici les Strings dans le tableau) en 2 puis encore en 2 etc pour "cerner" l'objectif et trouver rapidement la valeur recherchée.
Ici début, fin et milieu sont donc des positions dans le tableau.
cherche et t[x], avec x = milieu ou quelque position dans ce tableau, sont des Strings.
compareTo est une méthode, fonction ou opération selon le point de vue, qui s'applique à un objet, dans ce code de type String, pour retourner un résultat de comparaison. Son emploi est implicite dans A > B.
trouve est un témoin indiquant que la valeur de "cherche" existe dans au moins un élément du tableau t.

Donc, que vient faire resul dans cette recherche ? Et pourquoi y a-t-il une boucle for englobante ? La recherche dichotomique s'effectue dans la boucle while.

[antares56]

La recherche dichotomique joue sur la division de l'ensemble recherché (ici les Strings dans le tableau) en 2 puis encore en 2 etc pour "cerner" l'objectif et trouver rapidement la valeur recherchée.
Ici début, fin et milieu sont donc des positions dans le tableau.
cherche et t[x], avec x = milieu ou quelque position dans ce tableau, sont des Strings.
compareTo est une méthode, fonction ou opération selon le point de vue, qui s'applique à un objet, dans ce code de type String, pour retourner un résultat de comparaison. Son emploi est implicite dans A > B.
trouve est un témoin indiquant que la valeur de "cherche" existe dans au moins un élément du tableau t.

Donc, que vient faire resul dans cette recherche ? Et pourquoi y a-t-il une boucle for englobante ? La recherche dichotomique s'effectue dans la boucle while.

J'ai fait une boucle for englobant le tout pour faire int resul = cherche.compareTo(t[i]) ,en gros je voulais avec le for comparer cherche avec t[i] avec tout les éléments du tableau , stocker cette valeur dans "resul" et comparer resul avec le milieu du tableau, finalement comme tu dis ça n'a aucun sens

[Rony Rauzduel]

Bonjour,

Tu n'as pas à utiliser la méthode compareTo(T o), tu utilises tout simplement la recherche dichotomique classique.

Code Java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
for(int i =0;i<t.length;i++) {
    int resul = cherche.compareTo(t[i]);

à supprimer du code puis ajouter

Code Java :

Sélectionner tout - Visualiser dans une fenêtre à part

 return milieu

au dessous de

Code Java :

Sélectionner tout - Visualiser dans une fenêtre à part

trouve = true;

dès que la valeur est trouvée on la renvoi tout de suite.
Tu supprimes le test en fin de code, et tu retournes -1 si et seulement si tu n'a pas trouvé la valeur dans ton tableau.

[antares56]

Merci j'ai enfin trouver grâce à vous tous !