Recherche dichotomique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Dichotomie.
Visualisation d'une recherche dichotomique, où 4 est la valeur recherchée.

La recherche dichotomique, ou recherche par dichotomie[1] (en anglais : binary search), est un algorithme de recherche pour trouver la position d'un élément dans un tableau trié. Le principe est le suivant : comparer l'élément avec la valeur de la case au milieu du tableau ; si les valeurs sont égales, la tâche est accomplie, sinon on recommence dans la moitié du tableau pertinente.

Le nombre d'itérations de la procédure, c'est-à-dire le nombre de comparaisons, est logarithmique en la taille du tableau.

Exemple introductif[modifier | modifier le code]

On peut illustrer l'intérêt de la recherche dichotomique par l'exemple du jeu suivant.

A et B jouent au jeu suivant : A choisit un nombre entre 0 et 100, et ne le communique pas à B, B doit trouver ce nombre en posant des questions à A dont les réponses ne peuvent être que oui ou non. B doit essayer de poser le moins de questions possible.

Une stratégie pour B est d'essayer tous les nombres, mais il peut aller plus rapidement comme le montre le scenario suivant :

A choisit 66 et attend les questions de B :

  • B sait que le nombre est entre 0 et 100 ; au milieu se trouve 50, B demande donc : « Est-ce que le nombre est plus grand que 50? ». A répond « Oui ».
  • B sait maintenant que le nombre est entre 51 et 100 ; au milieu se trouve 75, il demande donc : « Est-ce que le nombre est plus grand que 75? » A répond « Non »
  • Et ainsi de suite : « Plus grand que 63? (63 =(51+75)÷2) », « Oui », « Plus grand que 69? (69 = (63+75)÷2)  », « Non », « Plus grand que 66? (66 = (69+63)÷2)  », « Non », « Plus grand que 65? (65 ≈ (63+66)÷2) », « Oui ».
  • B sait maintenant que le nombre est entre 66 et 66, autrement dit qu'il s'agit de 66 : il a trouvé le nombre choisi par A en seulement 7 questions.

Description de l'algorithme[modifier | modifier le code]

Principe[modifier | modifier le code]

L'algorithme est le suivant :

  • Trouver la position la plus centrale du tableau (si le tableau est vide, sortir).
  • Comparer la valeur de cette case à l'élément recherché.
  • Si la valeur est égale à l'élément, alors retourner la position, sinon reprendre la procédure dans la moitié de tableau pertinente.

On peut toujours se ramener à une moitié de tableau sur un tableau trié en ordre croissant. Si la valeur de la case est plus petite que l'élément, on continuera sur la moitié droite, c'est-à-dire sur la partie du tableau qui contient des nombres plus grands que la valeur de la case. Sinon, on continuera sur la moitié gauche.

Pseudo-code[modifier | modifier le code]

Écriture récursive[modifier | modifier le code]

On peut utiliser le pseudo-code suivant[2] :

recherche_dichotomique_récursive(élément, liste_triée):
   m = longueur de liste_triée / 2 ;
   si liste_triée[m] = élément :
       renvoyer m ;
   si liste_triée[m] > élément :
       renvoyer recherche_dichotomique_récursive(élément, liste_triée[1:m]) ;
   sinon :
       renvoyer recherche_dichotomique_récursive(élément, liste_triée[m:l]) ;

Écriture itérative[modifier | modifier le code]

L'algorithme de dichotomie permettant de trouver une valeur val dans un tableau t de N+1 entiers trié par ordre croissant est le suivant :

//déclarations
 début, fin, val, mil, N : Entiers
 t : Tableau [0..N] d'entiers classé
 trouvé : Booléen
 
//initialisation
 début ← 0 
 fin ← N
 trouvé ← faux
 Saisir val

//Boucle de recherche
  Répéter
   mil ← partie entière((début + fin)/2)
   Si t[mil] = val alors
     trouvé ← vrai
   Sinon
     Si val > t[mil] Alors
       début ← mil+1
       
     Sinon
       fin ← mil-1
       
     FinSi
    FinSi
   // La condition début inférieur ou égal à fin permet d'éviter de faire
   // une boucle infinie si 'val' n'existe pas dans le tableau.
   Tant que trouvé = faux ET début ≤ fin
//Affichage du résultat
Si trouvé Alors
     Afficher "La valeur ", val , " est au rang ", mil
  Sinon
     Afficher "La valeur ", val , " n'est pas dans le tableau"
FinSi

Variante pour recherche approchée[modifier | modifier le code]

On peut modifier l'algorithme pour faire des requêtes approchées, par exemple, quelle est la plus petite valeur strictement plus grande que a dans le tableau.

Complexité et performances[modifier | modifier le code]

La dichotomie possède une complexité algorithmique logarithmique en le nombre d'éléments composants le tableau dans lequel s'effectue la recherche[3],[4].

On considère dans un premier temps le nombre de comparaisons comme étant la mesure de complexité. On appelle T(n) le nombre de comparaisons effectuées pour une instance de taille n. Alors le nombre de comparaisons T satisfait la récurrence suivante : T(n)=1+T(n/2). Cette récurrence a une solution de la forme T(n)=O(log(n)), avec la notation de Landau. Enfin le nombre de comparaisons est linéaire en le nombre d'opérations effectuées; l'algorithme a donc une complexité logarithmique.

Comparaison avec d'autres méthodes[modifier | modifier le code]

Recherche séquentielle[modifier | modifier le code]

La méthode de recherche la plus simple est la recherche séquentielle qui s'effectue en temps linéaire : étudier les éléments les uns après les autres. Elle ne nécessite pas d'avoir une structure de données triée. De plus elle peut être pratiquée non seulement sur un tableau, mais aussi sur une liste chaînée, qui est parfois une structure plus adaptée. Sur des tableaux ordonnés, la recherche dichotomique est plus rapide asymptotiquement, mais pas forcément sur des tableaux de petite taille[5].

Hachage[modifier | modifier le code]

Le hachage est souvent plus rapide que la recherche dichotomique, avec une complexité amortie constante. La recherche dichotomique est cependant plus robuste en ce qu'elle peut être utilisée pour d'autres tâches qu'une simple recherche, comme trouver les éléments les plus proches d'un certain élément.

Arbre binaire de recherche[modifier | modifier le code]

Les arbres binaires de recherche utilisent une stratégie de dichotomie similaire à celle de la recherche dichotomique. La structure est plus efficace que les tableaux triés en ce qui concerne le temps d'insertion et de suppression (logarithmique et non binaire), mais ils prennent plus d'espace. De plus, si un tel arbre n'est pas parfaitement équilibré, alors la recherche dichotomique sur tableau sera plus rapide.

Recherche par interpolation[modifier | modifier le code]

Pour les tableaux triés dont les données sont régulièrement espacées, la recherche par interpolation est plus efficace.

Autre[modifier | modifier le code]

D'autres structures de recherches sont : les tableau de Judy (en)[6], les filtres de Bloom, les arbres de Van Emde Boas (en), arbres fusion (en), les tries et les tableaux de bits.

Champs d'application[modifier | modifier le code]

En dehors des considérations mathématiques, la méthode de détection de problème par dichotomie peut être appliquée à de nombreux processus.

Test dans l'industrie[modifier | modifier le code]

Par exemple, en industrie, si un produit passant par x phases de transformation présente une anomalie, il est très pratique d'utiliser la dichotomie pour analyser les transformations (ou processus) par groupe plutôt qu'un par un. Cela permet aussi d'effectuer des réglages précis par étape.

La méthode de dichotomie peut, par exemple, être utilisée si l'on rencontre un problème lorsque l'on groupe plusieurs appareils : on peut essayer de trouver le bon appareil en les triant et en faisant une dichotomie (en faisant des plus petits groupes).

Recherche de zéros[modifier | modifier le code]

La recherche par dichotomie peut être appliquée à la recherche des zéros approchés d'une fonction continue : il s'agit de la méthode de dichotomie.

Notes et références[modifier | modifier le code]

  1. Frédéric Fürst, « Recherche d'un élément », sur Université de Picardie.
  2. Xavier Dupré, « Recherche dichotomique, récursive, itérative et le logarithme »
  3. François Morain, « Introduction à la complexité des algorithmes : 7.3.2 Recherche dichotomique », sur École polytechnique (France), .
  4. « Algorithmes de recherche », sur Université de Lille
  5. (en) Donald E. Knuth, The Art of Computer Programming, vol. 3 : Sorting and Searching, , 2e éd. [détail de l’édition] §6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search".
  6. Julien Lemoine, « Structure de données en text mining », sur Laboratoire d'Informatique de Paris-Nord

Voir aussi[modifier | modifier le code]

Pages connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]