Recherche dichotomique
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. Il y a de nombreuses structures spécialisées (comme les tables de hachage) qui peuvent être recherchées plus rapidement, mais la recherche dichotomique s'applique à plus de problèmes.
Exemple introductif
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 1 et 20, et ne le communique pas à B, B doit trouver ce nombre en posant des questions à A dont les réponses ne peuvent être que « Non, plus grand », « Non, plus petit » ou « Oui, trouvé ». 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 scénario suivant :
A choisit 14 et attend les questions de B :
- B sait que le nombre est entre 1 et 20 ; au milieu se trouve 10 (ou 11), B demande donc : « Est-ce que le nombre est 10 ? ». A répond « Non, plus grand ».
- B sait maintenant que le nombre est entre 11 et 20 ; au milieu se trouve 15 (ou 16), il demande donc : « Est-ce que le nombre est 15 ? » A répond « Non, plus petit »
- Et ainsi de suite : « Est-ce 12 ? » (12 < (11+14)÷2 < 13), « Non, plus grand », « Est-ce 13? » (13 < (13+14)÷2 < 14), « Non, plus grand », « Est-ce bien 14 ? », « Oui, trouvé »
- B a trouvé le nombre choisi par A en seulement 5 questions.
Description de l'algorithme
Principe
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.
Écriture récursive
On peut utiliser un algorithme récursif comme l'implémentation en Python suivante [2] :
def recherche_dichotomique_recursive2(element, liste_triee):
if len(liste_triee)==1 :
return 0
m = len(liste_triee)//2
if liste_triee[m] == element :
return m
elif liste_triee[m] > element :
return recherche_dichotomique_recursive2(element, liste_triee[:m])
else :
return m + recherche_dichotomique_recursive2(element, liste_triee[m:])
Écriture itérative
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
// 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é != vrai et début <= fin:
mil ← partie_entière((début + fin)/2)
si t[mil] == val:
trouvé ← vrai
sinon:
si val > t[mil]:
début ← mil+1
sinon:
fin ← mil-1
//Affichage du résultat
Si trouvé == vrai:
Afficher "La valeur ", val , " est au rang ", mil
Sinon:
Afficher "La valeur ", val , " n'est pas dans le tableau"
Variante pour recherche approchée
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
La dichotomie possède une complexité algorithmique logarithmique en le nombre d'éléments composant 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). D'après le master theorem, 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.
D'autre part, pour déterminer la complexité de l'algorithme, on peut chercher à exprimer le nombre total d'opérations effectuées k (un entier naturel non nul) en fonction de la taille n de l'instance. De par le fonctionnement de la dichotomie, n est divisé par 2 à chaque itération de la boucle de recherche, la taille finale de l'instance est donc (en partie entière). Puisque la plus petite taille possible d'une instance est de 1, on a ; en multipliant par (positif) on obtient ; puis par composition avec le logarithme décimal (qui est croissant) ; enfin en divisant par non nul : . On obtient ainsi une complexité logarithmique.
Comparaison avec d'autres méthodes
Recherche séquentielle
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
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
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 linéaire), 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
Pour les tableaux triés dont les données sont régulièrement espacées, la recherche par interpolation est plus efficace.
Autre
D'autres structures de recherche sont : les matrices Judy[6], les filtres de Bloom, les arbres de Van Emde Boas, arbres fusion (en), les tries et les tableaux de bits.
Champs d'application
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
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
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
- Frédéric Fürst, « Recherche d'un élément », sur Université de Picardie.
- Xavier Dupré, « Recherche dichotomique, récursive, itérative et le logarithme »
- François Morain, « Introduction à la complexité des algorithmes : 7.3.2 Recherche dichotomique », sur École polytechnique (France), .
- « Algorithmes de recherche », sur Université de Lille
- (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".
- Julien Lemoine, « Structure de données en text mining », sur Laboratoire d'Informatique de Paris-Nord