Recherche dichotomique : couper en deux à chaque étape

Pour chercher une valeur dans un tableau quelconque, il faut au pire regarder toutes les cases : c'est le parcours séquentiel, de coût linéaire. Mais si le tableau est trié dans l’ordre croissant, on peut faire beaucoup mieux, comme on cherche un mot dans un dictionnaire.

On compare la valeur cherchée v à l'élément du milieu de la zone de recherche :

• s'il est égal à v, on a trouvé ;
• s'il est plus petit que v, v ne peut être qu'à droite du milieu : on garde la moitié droite ;
• s'il est plus grand, on garde la moitié gauche.

À chaque étape, la zone de recherche est au moins divisée par deux.

def recherche(t, v):
    debut = 0
    fin = len(t) - 1
    while debut <= fin:
        milieu = (debut + fin) // 2
        print(debut, fin, milieu, t[milieu])
        if t[milieu] == v:
            return milieu
        elif t[milieu] < v:
            debut = milieu + 1
        else:
            fin = milieu - 1
    return -1

t = [3, 8, 12, 17, 21, 26, 30, 34, 41, 47]
print(recherche(t, 34))

0 9 4 21
5 9 7 34
7

La ligne print(debut, fin, milieu, t[milieu]) affiche l'état de chaque tour : deux tours suffisent pour trouver 34, à l'indice 7.

Terminaison : un variant de boucle. La quantité fin - debut est un entier ; à chaque tour où la valeur n'est pas trouvée, elle diminue strictement, car debut devient milieu + 1 ou fin devient milieu - 1. Tant que la garde est vraie, fin − debut est en outre positif ou nul. Un entier non négatif ne peut pas décroître strictement indéfiniment : la condition debut <= fin finit donc par être fausse, ou un return termine la fonction.

C'est pour cela qu'on écrit milieu + 1 et milieu - 1, et non milieu : sans le « + 1 », la zone peut cesser de diminuer.

Valeur absente. Quand la zone devient vide (debut > fin), la fonction renvoie -1 :

def recherche(t, v):
    debut = 0
    fin = len(t) - 1
    while debut <= fin:
        milieu = (debut + fin) // 2
        if t[milieu] == v:
            return milieu
        elif t[milieu] < v:
            debut = milieu + 1
        else:
            fin = milieu - 1
    return -1

t = [3, 8, 12, 17, 21, 26, 30, 34, 41, 47]
print(recherche(t, 20))

-1

Coût logarithmique. Après un tour sans succès, une zone de L éléments en laisse au plus L // 2. Le nombre maximal de tours est donc le nombre de divisions par 2 qu'on peut faire avant d'atteindre 0 :

for n in [10, 1000, 1000000]:
    tours = 0
    taille = n
    while taille > 0:
        tours = tours + 1
        taille = taille // 2
    print(n, tours)

10 4
1000 10
1000000 20

Pour un tableau vide (n = 0), la boucle n’effectue aucun tour. Pour un million d’éléments, 20 tours au plus, contre un million pour un parcours séquentiel. Ce nombre de tours est le nombre de bits de n : c'est un coût en log₂(n).

Énoncé. Dans t = [3, 8, 12, 17, 21, 26, 30, 34, 41, 47], combien de tours fait la boucle pour trouver 12 ?

Trois tours. Remarquez que (0 + 3) // 2 vaut 1 : le quotient entier arrondit vers le bas.

À chaque tour, la taille passe de L à au plus L // 2 : 10, puis au plus 5, puis 2, puis 1. D'où au plus 4 tours pour 10 éléments.