Recherche dichotomique dans un tableau de String

Version imprimable

Bonjour à tous,

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

Code:

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?

05/11/2020, 10h02
Cincinnatus
Citation:

Envoyé par antares56

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:

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().
05/11/2020, 10h05
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 ?
05/11/2020, 10h34
Cincinnatus

Citation:

Envoyé par 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 ?

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.
05/11/2020, 14h28
antares56

Citation:

Envoyé par Cincinnatus

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
09/11/2020, 17h47
Rony Rauzduel
Bonjour,

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

1 2 3 for(int i =0;i<t.length;i++) { int resul = cherche.compareTo(t[i]);
à supprimer du code puis ajouter

Code:

return milieu

au dessous de

Code:

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.
11/11/2020, 02h16
antares56

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