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é.
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 ?
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.
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 :
| Essai | Proposition | Réponse | Intervalle restant |
|---|---|---|---|
| 1 | 50 | « C’est plus » | [51 ; 100] |
| 2 | 75 | « C’est moins » | [51 ; 74] |
| 3 | 62 | « C’est plus » | [63 ; 74] |
| 4 | 68 | « C’est plus » | [69 ; 74] |
| 5 | 71 | « C’est plus » | [72 ; 74] |
| 6 | 73 | « Trouvé ! » | — |
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.
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 :
centre = (debut + fin) // 2.liste[centre] à l’élément cherché :
debut = centre + 1 ;fin = centre - 1.debut <= fin. Si cette condition n’est plus vérifiée, l’élément est absent.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.
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.
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
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
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
À 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)\).
Ici, \(\log_2(n)\) est le logarithme de base 2 de \(n\), vu au chapitre Complexité : c’est l’exposant \(k\) tel que \(2^k = n\). Par exemple, \(\log_2(8) = 3\) et \(\log_2(1\,000\,000) \approx 19{,}9\). La notation \(\lfloor x \rfloor\) désigne la partie entière de \(x\), que Python calcule avec math.floor(x) : \(\lfloor 19{,}9 \rfloor = 19\).
Le nombre maximal d’étapes est donc \(\lfloor \log_2(n) \rfloor + 1\).
| Taille \(n\) | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 1 000 000 |
|---|---|---|---|---|---|---|---|---|---|
| Séquentielle (pire cas) | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 1 000 000 |
| Dichotomie (pire cas) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 20 |
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.
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.
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.
| Algorithme | Prérequis | Complexité (pire cas) | Étapes pour \(n = 10^6\) |
|---|---|---|---|
| Recherche séquentielle | Aucun | \(\mathcal{O}(n)\) | 1 000 000 |
| Recherche dichotomique | Liste triée | \(\mathcal{O}(\log_2 n)\) | 20 |
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.