Recherche dichotomique

Introduction

La recherche linéaire du cours 1 examine toutes les cases d'un tableau au pire. Pour 1 million d'éléments, c'est un million d'opérations. Si le tableau est trié, on peut faire spectaculairement mieux : c'est l'objet de la recherche dichotomique. L'idée est simple : comparer la cible à l'élément du milieu, et selon le résultat, jeter la moitié inutile. À chaque étape on divise par deux l'espace de recherche.

L'intuition « plus chaud, plus froid »

Le jeu est connu : un nombre est caché entre 1 et 100, et chaque proposition reçoit pour réponse « plus haut » ou « plus bas ». La stratégie optimale consiste à toujours proposer la moitié de l'intervalle restant.

• Au départ : 1 à 100. Proposition : 50.
• Réponse « plus haut » : 51 à 100. Proposition : 75.
• Réponse « plus bas » : 51 à 74. Proposition : 62.
• …

Sept questions au maximum suffisent. Pourquoi 7 ? Parce que $2^7 = 128 \geq 100$. Sept divisions par deux suffisent à isoler un nombre parmi 100. C'est exactement l'idée de la dichotomie.

L'algorithme

Prérequis : le tableau t doit être trié dans l'ordre croissant. Sinon l'algorithme ne fonctionne pas.

On maintient deux indices gauche et droite qui délimitent la zone où la cible pourrait encore se trouver. Tant que cette zone n'est pas vide :

1. on calcule l'indice du milieu, m = (gauche + droite) // 2 ;
2. si t[m] == cible, on a trouvé, on retourne m ;
3. si t[m] < cible, la cible est forcément à droite : on pose gauche = m + 1 ;
4. sinon, la cible est forcément à gauche : on pose droite = m - 1.

Si la zone devient vide (gauche > droite), la cible n'est pas dans le tableau.

def dichotomie(t, cible):
    """Retourne l'indice de cible dans t (trié), ou -1 si absente."""
    gauche, droite = 0, len(t) - 1
    while gauche <= droite:
        m = (gauche + droite) // 2
        if t[m] == cible:
            return m
        elif t[m] < cible:
            gauche = m + 1
        else:
            droite = m - 1
    return -1

trie = [1, 4, 7, 12, 18, 25, 33, 47, 58, 66, 80]
print(dichotomie(trie, 25))   # 5
print(dichotomie(trie, 10))   # -1

Le variant de boucle

Pour la dichotomie, le bon outil de raisonnement est le variant : une quantité qui décroît strictement à chaque tour et qui ne peut pas descendre indéfiniment.

On pose $v =$ droite - gauche. C'est la taille de la zone de recherche moins 1. À chaque tour :

• soit on trouve et on s'arrête (le while se termine par return),
• soit on fait gauche = m + 1, ce qui supprime au moins la moitié de l'intervalle ;
• soit on fait droite = m - 1, idem.

Dans tous les cas, $v$ diminue strictement. Comme $v$ est un entier, il finira par devenir négatif ($v < 0$, donc gauche > droite), ce qui arrête la boucle. L'algorithme termine donc toujours.

Pourquoi $\mathcal{O}(\log n)$ ?

À chaque tour, la taille de la zone de recherche est divisée par deux. En partant d'une zone de taille $n$ :

• après 1 tour : taille $n / 2$ ;
• après 2 tours : taille $n / 4$ ;
• après $k$ tours : taille $n / 2^k$.

On s'arrête quand cette taille atteint 0 ou 1, c'est-à-dire quand $2^k \geq n$. Le plus petit $k$ qui convient est $k = \lceil \log_2 n \rceil$. La complexité est donc logarithmique en $n$ :

Pièges courants

• Oublier que le tableau doit être trié : la dichotomie ne marche pas sur un tableau quelconque.
• m = (gauche + droite) / 2 au lieu de // 2 : la division / retourne un flottant en Python, qui ne peut pas servir d'indice.
• Bornes mal mises à jour : gauche = m au lieu de gauche = m + 1 cause des boucles infinies quand gauche == droite. La case m vient d'être testée, il faut l'exclure.
• Tableau vide : len(t) - 1 = -1, donc gauche = 0 > droite = -1, donc on n'entre pas dans la boucle, et on retourne -1. Cas géré sans cas particulier.

Pour aller plus loin

La dichotomie est l'archétype de la stratégie diviser pour régner, reprise en Terminale (tri fusion, tri rapide). À chaque étape, on réduit le problème à un sous-problème deux fois plus petit, jusqu'à un cas de base. Cette stratégie produit naturellement des complexités en $\mathcal{O}(\log n)$ ou $\mathcal{O}(n \log n)$.