Section courante

A propos

Section administrative du site

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
110 ≤ ⌈ Log2(1) ⌉
221 ≤ ⌈ Log2(2) ⌉
322 ≤ ⌈ Log2(3) ⌉
422 ≤ ⌈ Log2(4) ⌉
533 ≤ ⌈ Log2(5) ⌉
633 ≤ ⌈ Log2(6) ⌉
733 ≤ ⌈ Log2(7) ⌉
833 ≤ ⌈ Log2(8) ⌉
944 ≤ ⌈ Log2(9) ⌉
1044 ≤ ⌈ Log2(10) ⌉
1144 ≤ ⌈ Log2(11) ⌉
1244 ≤ ⌈ Log2(12) ⌉
1344 ≤ ⌈ Log2(13) ⌉
1444 ≤ ⌈ Log2(14) ⌉
1544 ≤ ⌈ Log2(15) ⌉
1644 ≤ ⌈ Log2(16) ⌉
1755 ≤ ⌈ Log2(17) ⌉
1855 ≤ ⌈ Log2(18) ⌉
1955 ≤ ⌈ Log2(19) ⌉
2055 ≤= ⌈ 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 :

  1. Program RechercheDichotomiqueSamples;
  2.  
  3. Const
  4.  n = 50;
  5.  
  6. Type
  7.  List50Integer=Array[1..n]of Integer;
  8. Var
  9.  Tableau:List50Integer;
  10.  I:Integer;
  11.  
  12. Function rechercheDichotomique(Const t:List50Integer;x:Integer):Integer;
  13. Var 
  14.  _min,_max,p:Integer;
  15. Begin
  16.    _min := 1;
  17.    _max := n;
  18.    While(_min <= _max)do Begin
  19.      p := (_min + _max) shr 1;
  20.      If t[p] = x Then Begin
  21.       rechercheDichotomique := p;
  22.       Exit;
  23.      End;
  24.      If t[p] < x Then _min := p + 1
  25.      Else _max := p - 1;
  26.    End;
  27.    rechercheDichotomique := -1;
  28. End;   
  29.  
  30. BEGIN
  31.  For I := 1 to 50 do Tableau[I] := I * 2;
  32.  WriteLn('10=',rechercheDichotomique(Tableau,10));
  33.  WriteLn('15=',rechercheDichotomique(Tableau,15));
  34.  WriteLn('20=',rechercheDichotomique(Tableau,20));
  35.  WriteLn('25=',rechercheDichotomique(Tableau,25));
  36.  WriteLn('30=',rechercheDichotomique(Tableau,30));
  37.  WriteLn('35=',rechercheDichotomique(Tableau,35));
  38. END.

on obtiendra le résultat suivant :

10=5
15=-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 :

  1. #define n 50
  2.  
  3. int Tableau[n];
  4.  
  5. int rechercheDichotomique(int t[],int x) {
  6.    int _min,_max,p;
  7.    _min = 1;
  8.    _max = n;
  9.    while(_min <= _max) {
  10.      p = (_min + _max) >> 1;
  11.      if(t[p] == x) return p;
  12.      else if(t[p] < x) _min = p + 1;
  13.      else _max = p - 1;
  14.    }
  15.    return -1;
  16. }
  17.  
  18. int main(void) {
  19.  for(int I = 1; I <= 50; I++) Tableau[I] = I * 2;
  20.  printf("10=%i\n",rechercheDichotomique(Tableau,10));
  21.  printf("15=%i\n",rechercheDichotomique(Tableau,15));
  22.  printf("20=%i\n",rechercheDichotomique(Tableau,20));
  23.  printf("25=%i\n",rechercheDichotomique(Tableau,25));
  24.  printf("30=%i\n",rechercheDichotomique(Tableau,30));
  25.  printf("35=%i\n",rechercheDichotomique(Tableau,35));
  26.  return 0;
  27. }

on obtiendra le résultat suivant :

10=5
15=-1
20=10
25=-1
30=15
35=-1

Dernière mise à jour : Mardi, le 18 avril 2017