Algorithme de recherche dichotomique

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.

Principe

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.

Algorithme récursif

Code générique (scriptol)

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.

• Script récursif complet.
• Code PHP.

Algorithme itératif

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.

• Script itératif complet.
• Code PHP.

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.

• Code source complet.
• Code PHP.

Performances et choix de l'algorithme

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.

Langages

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-dessus ne devrait pas poser de problème dans les autres langages de programmation.