Recherche dichotomique
Une recherche dans un tableau peut être une tâche très fastidieuse. Par exemple, la recherche d'un élément dans un tableau de 40000 entrées (un dictionnaire!) peut s'avérer catastrophique en temps si le mot recherché est justement le 40000ième. La recherche dichotomique est une technique algorithmique très efficace dans ces cas là
seulement pour les tableaux triés


Principe:
  • Comparer l'élément recherché avec l'élément au milieu du tableau.
  • Si l'élément recherché est plus petit que celui du milieu du tableau alors on est sûr que l'élément recherché ne peut pas être dans la seconde moitié du tableau et vice-versa.
  • On continue la recherche dans la moitié du tableau en appliquant le même principe. 
  • A force de découper le tableau en deux, on va soit trouver l'élément recherché soit se retrouver avec un seul élément qui ne sera pas l'élément recherché et la recherche sera infructueuse.

Regardons ce que cela donne en terme de nombre d'opérations à effectuer, en choisissant le pire cas : celui où le mot est absent du dictionnaire de 40000 mots
  • Au départ, on cherche le mot parmi 40 000
  • Après le test n°1, on ne le cherche plus que parmi 20 000
  • Après le test n°2, on ne le cherche plus que parmi 10 000
  • Après le test n°3, on ne le cherche plus que parmi 5 000
  • etc.
  • Après le test n°15, on ne le cherche plus que parmi 2.
  • Après le test n°16, on ne le cherche plus que parmi 1
Et on en déduit que le mot n'existe pas dans le dictionnaire ...
On a obtenu notre réponse en 16 opérations contre 40 000 pour une recherche classique

Exercice : Trouver un algorithme de la recherche dichotomique ...
suivant          plan