19 - Dichotomie

Chercher un élément dans une collection de données est l’une des opérations les plus fréquentes en informatique : trouver un mot dans un dictionnaire, un contact dans un répertoire, un livre dans une bibliothèque. Ce cours présente deux algorithmes de recherche et compare leur efficacité.

Recherche séquentielle

La méthode la plus naturelle pour chercher un élément dans une liste consiste à la parcourir du début à la fin en comparant chaque élément à la valeur cherchée. C’est la recherche séquentielle (ou recherche linéaire).

def chercher(liste, x):
    """Renvoie True si x est dans liste, False sinon."""
    for element in liste:
        if element == x:
            return True
    return False

Cette méthode fonctionne toujours, que la liste soit triée ou non. Mais elle peut être lente : dans le pire des cas (élément absent ou en dernière position), il faut examiner les \(n\) éléments de la liste. On dit que la complexité de la recherche séquentielle est en \(\mathcal{O}(n)\).

Question. Dans une liste de 1 000 000 d’éléments, combien de comparaisons faut-il au pire avec la recherche séquentielle ?

Peut-on faire mieux ?

Imaginez que l’on vous demande de trouver le mot « parallélisme » dans un dictionnaire de 1 000 pages. Vous ne commencez pas à la page 1 pour lire chaque entrée une par une. Vous ouvrez le dictionnaire vers le milieu, vous regardez où vous en êtes, puis vous continuez dans la bonne moitié. C’est exactement le principe de la recherche dichotomique.

Ce procédé ne fonctionne que si les éléments sont triés. Dans un dictionnaire, les mots sont classés par ordre alphabétique ; dans une liste Python, les valeurs doivent être rangées dans l’ordre croissant.

Le jeu du nombre mystère

Pour comprendre la dichotomie, jouons à un jeu. L’ordinateur choisit un nombre entre 1 et 100 et vous devez le deviner. À chaque essai, on vous dit « c’est plus » ou « c’est moins ».

Stratégie naïve : essayer 1, puis 2, puis 3… Au pire, 100 essais (recherche séquentielle).

Stratégie dichotomique : toujours proposer le milieu de l’intervalle restant.

Supposons que le nombre mystère est 73 :

En six essais, on a trouvé parmi 100 possibilités. Avec la recherche séquentielle, il aurait fallu 73 essais. À chaque étape, on élimine la moitié des possibilités.

Algorithme de recherche dichotomique

Principe

On dispose d’une liste triée dans l’ordre croissant. On maintient deux indices, debut et fin, qui délimitent la zone de recherche. À chaque étape :

1. On calcule l’indice du milieu : centre = (debut + fin) // 2.
2. On compare la valeur liste[centre] à l’élément cherché :
   • si elle est égale : l’élément est trouvé ;
   • si elle est inférieure : l’élément ne peut être que dans la moitié droite, donc debut = centre + 1 ;
   • si elle est supérieure : l’élément ne peut être que dans la moitié gauche, donc fin = centre - 1.
3. On recommence tant que debut <= fin. Si cette condition n’est plus vérifiée, l’élément est absent.

Exemple pas à pas

Cherchons la valeur 14 dans la liste triée [1, 2, 5, 9, 10, 14, 17, 24, 41].

Étape 1. debut = 0, fin = 8, centre = 4. La valeur centrale est liste[4] = 10.

 [1]  [2]  [5]  [9]  [10]  [14]  [17]  [24]  [41]
  0    1    2    3    ④     5     6     7     8
                     ↑ centre

Comme 10 < 14, on cherche dans la moitié droite : debut = 5.

Étape 2. debut = 5, fin = 8, centre = 6. La valeur centrale est liste[6] = 17.

                           [14]  [17]  [24]  [41]
                            5     ⑥     7     8
                                  ↑ centre

Comme 17 > 14, on cherche dans la moitié gauche : fin = 5.

Étape 3. debut = 5, fin = 5, centre = 5. La valeur centrale est liste[5] = 14.

                           [14]
                            ⑤
                            ↑ centre = trouvé !

L’élément 14 est trouvé en trois étapes, contre neuf au pire avec la recherche séquentielle.

Exemple avec un élément absent

Cherchons la valeur 7 dans la même liste [1, 2, 5, 9, 10, 14, 17, 24, 41].

Étape 1. centre = 4, liste[4] = 10. Comme 10 > 7, on prend la moitié gauche : fin = 3.

Étape 2. centre = 1, liste[1] = 2. Comme 2 < 7, on prend la moitié droite : debut = 2.

Étape 3. centre = 2, liste[2] = 5. Comme 5 < 7, on prend la moitié droite : debut = 3.

Étape 4. centre = 3, liste[3] = 9. Comme 9 > 7, on prend la moitié gauche : fin = 2.

Maintenant debut = 3 > fin = 2 : la condition debut <= fin n’est plus vérifiée. L’élément 7 est absent de la liste. On a eu besoin de quatre étapes pour le déterminer.

Implémentation en Python

Version booléenne

def recherche_dichotomique(liste, element):
    """Renvoie True si element est dans liste (triée), False sinon."""
    debut = 0
    fin = len(liste) - 1
    while debut <= fin:
        centre = (debut + fin) // 2
        if liste[centre] == element:
            return True
        elif liste[centre] < element:
            debut = centre + 1
        else:
            fin = centre - 1
    return False

Version renvoyant l’indice

def indice_dichotomie(liste, element):
    """Renvoie l'indice de element dans liste (triée), ou None si absent."""
    debut = 0
    fin = len(liste) - 1
    while debut <= fin:
        centre = (debut + fin) // 2
        if liste[centre] == element:
            return centre
        elif liste[centre] < element:
            debut = centre + 1
        else:
            fin = centre - 1
    return None

Vérification

L = [1, 2, 5, 9, 10, 14, 17, 24, 41]

print(recherche_dichotomique(L, 14))   # True
print(recherche_dichotomique(L, 7))    # False

print(indice_dichotomie(L, 14))        # 5
print(indice_dichotomie(L, 7))         # None

Complexité

À chaque étape, la taille de la zone de recherche est divisée par deux. Après \(k\) étapes, il reste au plus \(\dfrac{n}{2^k}\) éléments à explorer. La recherche se termine lorsque cette quantité est inférieure à 1, c’est-à-dire lorsque \(k > \log_2(n)\).

Le nombre maximal d’étapes est donc \(\lfloor \log_2(n) \rfloor + 1\).

La recherche séquentielle a une complexité en \(\mathcal{O}(n)\) (linéaire). La recherche dichotomique a une complexité en \(\mathcal{O}(\log_2 n)\) (logarithmique).

Pour une liste d’un million d’éléments, la dichotomie nécessite au plus 20 comparaisons contre un million pour la recherche séquentielle.

Terminaison de l’algorithme

Il est important de vérifier que la boucle while se termine toujours. Considérons le variant de boucle \(v = \texttt{fin} - \texttt{debut} + 1\), le nombre d’éléments restant à examiner.

À chaque tour de boucle, soit on trouve l’élément (et on sort), soit on met à jour debut ou fin de sorte que l’écart \(v\) diminue strictement d’au moins 1. Comme \(v\) est un entier positif qui diminue strictement, la boucle se termine en un nombre fini d’étapes.

Conditions d’utilisation

La recherche dichotomique ne fonctionne que si la liste est triée. Si la liste n’est pas triée, le résultat peut être incorrect : l’algorithme peut déclarer absent un élément qui est pourtant présent.

C’est un compromis classique en algorithmique : on investit du temps une fois pour trier la liste, puis on bénéficie de recherches très rapides par la suite.

Résumé

La recherche dichotomique divise la zone de recherche par deux à chaque étape. Elle exige une liste triée et offre une complexité logarithmique, spectaculairement plus efficace que la recherche séquentielle pour les grandes listes.