Recherche dichotomique

On a vu dans le chapitre sur les listes, que la complexité de l'algorithme de recherche d'un élément dans la liste est linéaire. Ce qui signifie que pour chercher un élément dans une liste de taille n il peut être nécessaire de faire n comparaisons.

Ce chapitre est consacré à un algorithme beaucoup plus rapide mais qui ne s'applique qu'à des listes triées.

I/ Principe

• On regarde l'élément médian (celui du milieu de la liste).
• On le compare avec l'élément cherché :
• Si ce dernier est égal à l'élément médian, l'algorithme se termine sur une réponse positive.
• S'il est plus grand que l'élément cherché, c'est que l'élément cherché ne peut pas être dans la moitié droite de la liste triée. On supprime donc la moitié droite de la liste et l'élément médian.
• S'il est plus petit que l'élément cherché, c'est que l'élément cherché ne peut pas être dans la moitié gauche de la liste triée. On supprime donc la moitié gauche de la liste et l'élément médian.
• On recommence tout ce qui précède sur la liste restante, jusqu'à ce que cette liste soit devenue vide.

II/ Code Python

1) Moitié gauche de la liste

On construit par compréhension la liste des éléments de L jusqu'à celui dont le rang est immédiatement inférieur au milieu de la liste :

def moitié_gauche(L: list) -> list:
    return [L[k] for k in range(milieu)]

2) Moitié droite de la liste

On construit par compréhension la liste des éléments de L à partir de celui dont le rang est immédiatement supérieur au milieu de la liste :

def moitié_droite(L: list) -> list:
    return [L[k] for k in range(milieu+1,len(L))]

3) Recherche dichotomique dans la liste triée

def contient(L: list, elt: int):
    assert L==sorted(L)
    while len(L)>0:
        milieu = len(L)//2
        mediane = L[milieu]
        if elt==mediane:
            return True
        elif elt<=mediane:
            L = moitié_gauche(L)
        else:
            L = moitié_droite(L)
    return False

Remarque : on gagne en rapidité si, au lieu de supprimer la moitié de la liste (ce qui prend du temps) on s'arrange pour ne plus la regarder. Ceci nécessite de compléter la variable milieu par une autre variable entière. De plus, le fait de ne pas détruire la liste permet de refaire une recherche ultérieure dans la même liste, ce qui est fréquent dans les Big Data.

III/ Propriétés

1) Invariant

La phrase « si l'élément est dans la liste de départ, alors il est forcément dans la sous-liste en cours de traitement » est un invariant de la boucle.

L'algorithme effectue bien une recherche dans la liste triée. Il est correct.

2) Variant

On peut prouver la correction et la terminaison avec why3.

Là encore, la taille de la liste restant à traiter est un variant de la boucle : l'algorithme se termine au bout d'un temps fini. On estime ce temps avec plus de précision dans le paragraphe suivant.

3) Complexité

À chaque passage dans la boucle, la longueur de la liste est divisée par 2 (c'est pour ça que cette longueur est un variant de boucle). On peut donc calculer le nombre de comparaisons en comptant le nombre de divisions par 2 qui aboutissent à une liste vide. Avec une variable compteur on peut même demander à Python de compter :

def nombre_de_comparaisons(longueur):
    compteur = 0
    while longueur>0:
        compteur += 1
        longueur //= 2
    return compteur

Voici la représentation graphique de cette fonction. On y voit notamment que

• Il n'y a qu'une comparaison à effectuer si la liste est de longueur 1.
• Il n'y a que 2 comparaisons à effectuer si la liste est de longueur 2 ou 3.
• Pour une liste de longueur 42 par exemple, il n'y a que 6 comparaisons à effectuer :

Remarque :

En binaire, 42 s'écrit 101010 qui comprend 6 bits. Plus généralement, le nombre de comparaisons à effectuer dans une liste de taille n est égal au nombre de chiffres binaires de n.

Ce résultat est lié au fait qu'en binaire, la division par 2 supprime le chiffre de droite. Le nombre de chiffres binaires d'un entier s'appelle son logarithme. Cette notion est à la base des travaux de Claude Shannon. En Python on peut connaître le nombre de chiffres binaires d'un entier n en faisant :

from math import log
def nombre_de_chiffres(n: int) -> int:
    return int(log(n)/log(2))

La liste [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987] dessinée ci-dessous montre les parcours permettant de savoir si un nombre est dans la liste :