La recherche dichotomique (binary search) en Python
Dans cette leçon, vous allez implémenter la recherche dichotomique pour trouver rapidement une valeur dans une liste triée.
Introduction
Le problème
Pour trouver une valeur dans une liste d'un million d'éléments en les vérifiant un par un, il faut parfois un million de comparaisons. Quand la liste est triée, on peut faire bien mieux : une vingtaine de comparaisons suffisent, car chacune élimine la moitié de ce qui reste.
Imaginez-le ainsi
La recherche dichotomique, c'est ce que vous faites pour chercher un mot dans un dictionnaire papier. Vous l'ouvrez au milieu, vous regardez si votre mot vient avant ou après cette page, et vous écartez la moitié qui ne peut pas le contenir. Vous recommencez avec la moitié restante jusqu'à tomber sur le mot.
low, high = 0, len(values) - 1📖 Les pages où il reste à cherchermiddle = (low + high) // 2👆 Ouvrir au milieulow = middle + 1➡️ Le mot vient après : écarter la première moitiéhigh = middle - 1⬅️ Le mot vient avant : écarter la seconde moitiéLa recherche dichotomique trouve une valeur dans une liste triée : elle la compare à l'élément du milieu, écarte la moitié qui ne peut pas la contenir, puis recommence. Elle prend O(log n) étapes.
Points clés
lowethighdélimitent la partie de la liste qui peut encore contenir la cible.middle = (low + high) // 2choisit l'indice du milieu de cette partie.- Si
values[middle] < target, la cible est à droite, donclow = middle + 1; sinonhigh = middle - 1. while low <= high:s'arrête quand la plage est vide, et la fonction renvoie-1si elle n'a rien trouvé.- Pour 17, la recherche vérifie 12, puis 25, puis 17 : trois comparaisons au lieu de quatre.
Quand l’utiliser ?
- Chercher dans de gros volumes de données triées : identifiants, dictionnaires, journaux (logs) triés.
- Trouver où insérer une valeur pour qu'une liste reste triée.
- Les jeux de devinettes et tout problème où l'on cerne la réponse à coups de plus haut ou plus bas.
Quand s'en passer
- Les données ne sont pas triées : trier juste pour chercher une fois coûte plus cher qu'une recherche linéaire.
- Les petites listes ou les recherches ponctuelles :
inou un dictionnaire est plus simple. Pour de nombreuses recherches par clé, un dict ou un set est encore plus rapide.
Visualisation de La recherche dichotomique (binary search) en Python
O(log n)Utilisez Lecture ou Étape pour suivre chaque comparaison et déplacement de données.
Code d’exemple
def binary_search(values, target):
low, high = 0, len(values) - 1
while low <= high:
middle = (low + high) // 2
if values[middle] == target:
return middle
if values[middle] < target:
low = middle + 1
else:
high = middle - 1
return -1
print(binary_search([3, 8, 12, 17, 25, 31], 17))
Résultat de l’exécution
3
Explication du code
Les variables low et high délimitent la zone qu'il reste à explorer. Si l'élément du milieu est plus petit que la valeur cherchée, l'algorithme écarte la moitié gauche avec low = middle + 1, sinon il écarte la moitié droite. La complexité en temps est O(log n), à condition que la liste d'entrée soit déjà triée.
Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.
Exercices d’approfondissement
Essayez de modifier le code en suivant les pistes ci-dessous. Changer le code et observer le résultat vous fera bien mieux comprendre la leçon que la simple lecture.
- Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
- Affichez l’état après chaque étape pour observer l’algorithme en action.
- Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Erreurs fréquentes
Utiliser < au lieu de <= dans la boucle
Avec low < high, la dernière position restante n'est jamais vérifiée, même si la cible s'y trouve.
while low < high:
while low <= high:
Ne pas avancer au-delà du milieu
Avec low = middle, la boucle peut retomber sans fin sur le même milieu.
low = middle
low = middle + 1
Leçon terminée ?
Marquez-la comme apprise pour suivre votre progression.
S'entraîner avec un défi
Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.
- Temps de Production en Usine Trouvez le temps le plus tôt auquel des machines parallèles peuvent terminer un nombre cible d’objets. Moyen
- Median of Two Sorted Arrays Find the median of two sorted lists combined. Difficile