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[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 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[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.

Algorithme et implémentation[modifier | modifier le code]

Algorithme[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
 N = taille(t)-1
 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"

Implementation[modifier | modifier le code]

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:])

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. En voici une implementation en Python:

def plus_petit_successeur(element, liste_triee):
    assert element <= liste_triee[len(liste_triee)-1], (
    "L'élément n'a pas de successeur dans la liste.")
    gauche = 0
    droite = len(liste_triee) - 1
    m = (gauche + droite) // 2  # Milieu
    while gauche <= droite:
        if liste_triee[m] == element:
            return liste_triee[m]
        elif liste_triee[m] > element:
            droite = m - 1
        else:
            gauche = m + 1
        m = (gauche + droite) // 2
    # On sort de la boucle si l'élément recherché n'est pas dans la liste
    return liste_triee[m + 1]
‎

Complexité et performances[modifier | modifier le code]

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 $\lfloor n/2^{k}\rfloor$ (en partie entière). Puisque la plus petite taille possible d'une instance est de 1, on a $1\leqslant n/2^{k}$ ; en multipliant par $2^{k}$ (positif) on obtient $2^{k}\leqslant n$ ; puis par composition avec le logarithme décimal (qui est croissant) $k\times \log(2)\leqslant \log(n)$ ; enfin en divisant par $\log(2)$ non nul : $k\leqslant \log(n)/\log(2)=\log _{2}(n)$ . On obtient ainsi 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 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[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 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[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]

↑ 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), 2004.
↑ « Algorithmes de recherche », sur Université de Lille
↑ (en) Donald E. Knuth, The Art of Computer Programming, vol. 3 : Sorting and Searching, 1998, 2^e é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

Voir aussi[modifier | modifier le code]

Pages connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]

Severance, « Recherche dichotomique », sur OpenClassrooms, octobre 2013

Portail de l'informatique théorique

[picardie-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), 2004.

[4] « Algorithmes de recherche », sur Université de Lille

[5] (en) Donald E. Knuth, The Art of Computer Programming, vol. 3 : Sorting and Searching, 1998, 2^e é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

[1]

[2]

[3]

[4]

[5]

[6]