Algorithme de recherche dichotomique

La recherche dichotomique est nettement plus rapide qu'une recherche linéaire consistant à comparer avec les éléments successivement dans la liste, sauf si la liste est très courte ou si l'élément cherché se trouve en tête de liste, ce qui n'est normalement pas prévisible.

Cet algorithme opère sur un ensemble ordonné et se sert de l'ordre pour diriger la recherche. Le mot dichotomie vient du grec διχοτόμηση qui signifie: couper en deux.

Le langage C++ fournit une fonction binary_search dans la librairie STL.
Le framework .NET dispose de fonctions similaire dans les bibliothèques de base (System.Array).
Adapter le code générique ci-dessous ne devrait pas poser de problème dans les autres langages de programmation.

Principe de l'algorithme

Comment trouver rapidement le mot Untel dans un dictionnaire? On ouvre le livre au milieu et l'on tombe sur les mots commençant par m, lettre qui se trouve au centre du dictionnaire. On voit que untel ne peut figurer dans la première moitié, donc on restreint la recherche à la seconde qui va de m à z.
On met donc de coté la première moitié et on effectue le même raisonnement sur la seconde et ainsi de suite sur chaque nouvelle partie, on réduit progressivement la liste en allant soit dans la partie gauche, soit dans la partie droite, pour parvenir inéluctablement à la page contenant le mot cherché.

Le principe de recherche dichotomique peut se généraliser à tout type de problème dès lors que les objets du champ de recherche puissent former une séquence et qu'il soit possible d'effectuer une comparaison relative à l'ordre dans la séquence.

Implémenter l'algorithme sur ordinateur est facile grâce à la récursivité, mais il peut s'implémenter également de façon itérative.

Version récursive

Code générique (scriptol):

array A = []

int binarySearch(int value, int starting, int ending)
  if ending < starting return -1
  int mid = (starting + ending)  / 2	
  if A[mid]
      = value :     return mid
      > value :     ending = mid - 1
      < value :     starting = mid + 1   
  /if	 
return  binarySearch(value, starting, ending)

Le tableau A est parcouru en tant que variable globale ce qui accélère énormément l'exécution du script, et les variables d'indice starting et ending sont utilisées pour sélectionner une tranche progressivement réduite du tableau.

Application à un tableau de texte

Code de l'algorithme:

int binarySearch(text value, int starting, int ending)
  if ending < starting return -1
  int mid = (starting + ending)  / 2
  int result = strcmp(value, A[mid])  	

  if result
  = 0 :  return mid
  < 0 :  ending = mid - 1
  > 0 :  starting = mid + 1   
  /if
return  binarySearch(value, starting, ending)

Seule la fonction de comparaison a changé. La fonction strcmp retourne 0 quand les chaînes sont identiques, un nombre inférieur à 0 si la première se classe avant la seconde et supérieur à 0 dans le cas contraire.

Version itérative

Code générique (scriptol):

int binarySearch(int value, array A)
  int starting = 0
  int ending = A.size() 
  int mid
  int length
  
  while forever  
      if starting > ending return -1   
      length = ending - starting 

      if length = 0
          if value = A[starting] return starting
          return -1 
       /if	 
      mid = starting + int(length / 2)

      if value 
          < A[mid] : ending = mid - 1
          > A[mid] : starting = mid + 1
      else
           return mid
      /if
  /while
return -1

L'exemple utilise le tableau comme paramètre de la fonction, mais on pourrait aussi bien l'utiliser en tant que variable globale comme avec l'algorithme récursif.