Prog-Info > C++ > Tri et Recherche > Dichotomie.

---

La dichotomie

La recherche binaire : la dichotomie n'est appliquable que si le tableau a été trié auparavant. Cet algorithme commence par l'élément central et le compare à la clef recherché. Si les deux valeurs sont égales alors la valeur de l'indice est retournée. Si l'élément recherché est inférieur, la recherche est poursuivie de manière analogue dans la première partie du tableau. Sinon elle est supérieure et la recherche se poursuit dans seconde partie du tableau. La recherche continue jusqu'à ce que la clef soit égale à l'élément central d'un sous tableau ou jusqu'à ce que le sous tableau comporte un élément dont la valeur diffère de celle de la clef de recherche c'est à dire que la clef recherchée n'a pas été trouvée.

int rechercheBinaire(const int tableau[], const int longueur,                       const int clef, int inferieur, int superieur) {    int centre;    while(bas <= haut)    {       centre = (bas+haut)/2; // élément central de la partie traité       if(cleRecherche == b[centre]) // valeur trouvée          return centre;       else if(cleRech erche < b[centre])          haut = centre-1; // recherche ds la partie inférieure du tableau       else          bas = centre+1; // recherche ds la partie supérieure du tableau    }    return -1; // valeur recherchée non trouvée }

Exemple :
La valeur recherchée est 8.
Les cases colorées en vert indiquent dans quelle partie va s'effectuer la recherche et les cases colorées en bleues montrent l'élément central.

0	1	2	3	4	5	6	7	8	9
0	1	2	3	4	5	6	7	8	9
0	1	2	3	4	5	6	7	8	9
0	1	2	3	4	5	6	7	8	9
0	1	2	3	4	5	6	7	8	9
0	1	2	3	4	5	6	7	8	9

La valeur a été trouvée ; la fonction retourne la position de cette valeur, qui dans notre cas est 8.

Complexité :
Cet algorithme est très efficace pour les grands tableaux car il élimine à chaque passage la moitié du tableau par une simple comparaison (à condition que le tableau soit trié, bien sûr).
Par exemple, sur un tableau de 1024 éléments, dans le pire des cas il aura fallut 10 comparaisons (en remarquant que 1024 = 2^10). Si on prend un tableau de 1 048 576 (2^20), il faudra au maximum 20 comparaisons pour trouver la valeur recherchée ou pour montrer qu'elle ne s'y trouve pas.