Introduction
La recherche dichotomique, surnommé la recherche binaire ou recherche logarithmique, est un algorithme de recherche très rapide pour trouver de l'information dans un grand tableau.
Tout d'abord, il faut savoir que cette algorithme fonctionne uniquement si les données sont ordonnées. Les données peuvent être aussi bien des nombres que des caractères.
Ensuite, le principe réside dans le fait qu'on divise toujours par deux le tableau la recherche d'un valeur dans le tableau de façon récursive. Ainsi, par exemple, sur 128 éléments, lors de la première comparaison, on divise par 2, on se retrouve avec une portion de 64 éléments, ensuite, lors de la deuxième comparaison, on divise par 2, on se retrouve avec une portion de 32 éléments, lors de la troisième comparaison, on passe avec une portion de 16 éléments, à la quatrième comparaison, on passe avec une portion de 8 éléments, à la cinquième comparaison, on passe avec une portion de 4 éléments, à la sixième comparaison, on passe avec une portion de 2 éléments, à la septième comparaison, il reste qu'avec un élément. Ainsi, sur 128 possibilités, il n'aura fallu que 7 comparaisons pour trouver la valeur, au lieu de parcourir les 128 cellules du tableau une par une !
Estimation du nombres de comparaison
Sachant que «r» est le nombre de comparaison maximum, et que «r» est tel que 2r ≤ n < 2r+1, on aura donc la formule d'estimation suivante :
| r ≤ ⌈ Log2(n) ⌉ |
Et pourra déterminer le tableau suivant :
| Nombre d'éléments | Nombre de comparaison maximum | Formule d'estimation |
|---|---|---|
| 1 | 1 | 0 ≤ ⌈ Log2(1) ⌉ |
| 2 | 2 | 1 ≤ ⌈ Log2(2) ⌉ |
| 3 | 2 | 2 ≤ ⌈ Log2(3) ⌉ |
| 4 | 2 | 2 ≤ ⌈ Log2(4) ⌉ |
| 5 | 3 | 3 ≤ ⌈ Log2(5) ⌉ |
| 6 | 3 | 3 ≤ ⌈ Log2(6) ⌉ |
| 7 | 3 | 3 ≤ ⌈ Log2(7) ⌉ |
| 8 | 3 | 3 ≤ ⌈ Log2(8) ⌉ |
| 9 | 4 | 4 ≤ ⌈ Log2(9) ⌉ |
| 10 | 4 | 4 ≤ ⌈ Log2(10) ⌉ |
| 11 | 4 | 4 ≤ ⌈ Log2(11) ⌉ |
| 12 | 4 | 4 ≤ ⌈ Log2(12) ⌉ |
| 13 | 4 | 4 ≤ ⌈ Log2(13) ⌉ |
| 14 | 4 | 4 ≤ ⌈ Log2(14) ⌉ |
| 15 | 4 | 4 ≤ ⌈ Log2(15) ⌉ |
| 16 | 4 | 4 ≤ ⌈ Log2(16) ⌉ |
| 17 | 5 | 5 ≤ ⌈ Log2(17) ⌉ |
| 18 | 5 | 5 ≤ ⌈ Log2(18) ⌉ |
| 19 | 5 | 5 ≤ ⌈ Log2(19) ⌉ |
| 20 | 5 | 5 ≤= ⌈ Log2(20) ⌉ |
| ... | ... | ... |
Sachant que le tableau T de n éléments (triées) selon la condition suivante :
| clef(t[1]) < clef(t[2]) < ... < clef(t[n]) |
Aussi, les variables «min» et «max» permettent d'indiquer la limite de la portion de comparaison dans «t» a effectuer. De cette façon, à tout moment, la position «p» de la clef «x» est connu entre l'intervalle de «min» et «max» : min < p < max.
Algorithme
Voici donc son algorithme :
|
MODULE rechercheDichotomique(t[1...n],x) min ← 1 max ← n BOUCLE TANT QUE min ≤ max p ← (min + max) ÷ 2 SI t[p] = x ALORS RETOURNER p FIN SI SI t[p] ≤ x ALORS min ← p + 1 SINON t[p] >= x ALORS max ← p - 1 FIN SI FIN TANT QUE RETOURNER -1 |
Exemples
L'exemple suivant, écrit en Free Pascal, construire un tableau de suite de 50 nombres paires et retourne la position de certains nombres de ceux-ci en utilisant la recherche dichotomique :
- Program RechercheDichotomiqueSamples;
-
- Const
- n = 50;
-
- Type
- List50Integer=Array[1..n]of Integer;
- Var
- Tableau:List50Integer;
- I:Integer;
-
- Function rechercheDichotomique(Const t:List50Integer;x:Integer):Integer;
- Var
- _min,_max,p:Integer;
- Begin
- _min := 1;
- _max := n;
- While(_min <= _max)do Begin
- p := (_min + _max) shr 1;
- If t[p] = x Then Begin
- rechercheDichotomique := p;
- Exit;
- End;
- If t[p] < x Then _min := p + 1
- Else _max := p - 1;
- End;
- rechercheDichotomique := -1;
- End;
-
- BEGIN
- For I := 1 to 50 do Tableau[I] := I * 2;
- WriteLn('10=',rechercheDichotomique(Tableau,10));
- WriteLn('15=',rechercheDichotomique(Tableau,15));
- WriteLn('20=',rechercheDichotomique(Tableau,20));
- WriteLn('25=',rechercheDichotomique(Tableau,25));
- WriteLn('30=',rechercheDichotomique(Tableau,30));
- WriteLn('35=',rechercheDichotomique(Tableau,35));
- END.
on obtiendra le résultat suivant :
10=515=-1
20=10
25=-1
30=15
35=-1
L'exemple suivant, écrit en C, construire un tableau de suite de 50 nombres paires et retourne la position de certains nombres de ceux-ci en utilisant la recherche dichotomique :
- #define n 50
-
- int Tableau[n];
-
- int rechercheDichotomique(int t[],int x) {
- int _min,_max,p;
- _min = 1;
- _max = n;
- while(_min <= _max) {
- p = (_min + _max) >> 1;
- if(t[p] == x) return p;
- else if(t[p] < x) _min = p + 1;
- else _max = p - 1;
- }
- return -1;
- }
-
- int main(void) {
- for(int I = 1; I <= 50; I++) Tableau[I] = I * 2;
- printf("10=%i\n",rechercheDichotomique(Tableau,10));
- printf("15=%i\n",rechercheDichotomique(Tableau,15));
- printf("20=%i\n",rechercheDichotomique(Tableau,20));
- printf("25=%i\n",rechercheDichotomique(Tableau,25));
- printf("30=%i\n",rechercheDichotomique(Tableau,30));
- printf("35=%i\n",rechercheDichotomique(Tableau,35));
- return 0;
- }
on obtiendra le résultat suivant :
10=515=-1
20=10
25=-1
30=15
35=-1