L'exemple roi : la recherche dichotomique

Chercher dans un annuaire trié

Voici le meilleur exemple pour ressentir la différence entre O(n) et O(log n). On cherche un nombre dans une liste triée.

La méthode naïve, dite recherche linéaire, examine les éléments un par un : O(n). Dans le pire cas (élément absent), elle lit toute la liste.

La méthode maligne, la recherche dichotomique, exploite le tri : on regarde l'élément du milieu, et selon qu'il est trop grand ou trop petit, on élimine la moitié de la liste d'un seul coup.

Le schéma : chercher 7 dans une liste triée

Liste :  [1] [3] [4] [7] [9] [11] [15] [20]
                          ^milieu = 9
   7 < 9  ->  on jette toute la moitie DROITE

Reste :  [1] [3] [4] [7]
                  ^milieu = 4  (ou 3, selon l'arrondi)
   7 > 4  ->  on jette la moitie GAUCHE

Reste :          [7]
                  ^ trouve en 3 etapes !

Sur 8 éléments, 3 étapes ont suffi. Ce n'est pas un hasard : 8 = 2^3, et log2(8) = 3.

Le code

def dichotomie(liste_triee, cible):
    gauche, droite = 0, len(liste_triee) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if liste_triee[milieu] == cible:
            return milieu
        elif liste_triee[milieu] < cible:
            gauche = milieu + 1       # (jeter la moitie gauche)
        else:
            droite = milieu - 1       # (jeter la moitie droite)
    return -1                          # (absent)

Pourquoi c'est du O(log n)

À chaque tour de boucle, la zone de recherche est divisée par deux. La question devient : combien de fois peut-on diviser n par 2 avant d'arriver à 1 ? Réponse : log2(n) fois. C'est la définition même du logarithme.

   n = 1 000 000 elements
   recherche lineaire   : jusqu'a 1 000 000 comparaisons
   recherche dichotomique : ~20 comparaisons  (car 2^20 > 1 000 000)

Vingt comparaisons contre un million. Et pour un milliard d'éléments ? À peine 30. Le logarithme grandit si lentement que multiplier la taille par 1000 n'ajoute que 10 comparaisons.

Le prix à payer

La dichotomie exige que la liste soit triée au préalable. C'est le compromis classique : on investit une fois dans le tri (O(n log n)) pour ensuite chercher des milliers de fois en O(log n). C'est exactement le principe d'un dictionnaire ou d'un annuaire : on le maintient trié précisément pour pouvoir y chercher vite.

En résumé

La recherche dichotomique divise par deux la zone de recherche à chaque étape, atteignant une complexité O(log n) — une vingtaine de comparaisons pour un million d'éléments, contre un million pour la recherche linéaire O(n). Son unique condition : la liste doit être triée. C'est l'illustration parfaite de la puissance d'un O(log n).