La recherche dichotomique : retrouver une aiguille dans 1 million de pailles

Le jeu du « plus ou moins »

Je pense à un nombre entre 1 et 100. Tu proposes 50 : « plus grand ». Tu proposes 75 : « plus petit »… En 7 essais maximum tu trouves, parce que chaque réponse élimine la moitié des possibilités. Voilà la recherche dichotomique : sur une liste triée, on regarde l’élément du milieu et on garde la bonne moitié.

Choisis une cible et avance étape par étape : la zone grisée est éliminée à chaque comparaison.

L’algorithme

def dichotomie(liste, cible):
    bas, haut = 0, len(liste) - 1
    etapes = 0
    while bas <= haut:
        milieu = (bas + haut) // 2
        etapes += 1
        if liste[milieu] == cible:
            return milieu, etapes
        elif liste[milieu] < cible:
            bas = milieu + 1       # on garde la moitié droite
        else:
            haut = milieu - 1      # on garde la moitié gauche
    return -1, etapes              # absent

donnees = list(range(0, 2000, 2))   # 1000 nombres pairs triés
print(dichotomie(donnees, 1234))    # trouvé en peu d'étapes
print(dichotomie(donnees, 1235))    # absent : (-1, ...)

Pour 1 000 éléments : au plus 10 étapes. Pour 1 milliard : au plus 30. Doubler la taille ne coûte qu’une étape de plus : c’est le sens de O(log n).

Les conditions de réussite

• La liste doit être triée. Sinon, éliminer une moitié n’a aucun sens.
• Accès direct par position : parfait sur un tableau, inefficace sur une liste chaînée.
• Bornes soignées : bas + 1 et haut - 1 garantissent que l’intervalle se réduit toujours, donc que la boucle se termine.