Algorithmes Python

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.

  • Intermédiaire
  • 2 min de lecture
  • 1 exemple exécutable

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.

Du dictionnaire papier au code
low, high = 0, len(values) - 1📖 Les pages où il reste à chercher
middle = (low + high) // 2👆 Ouvrir au milieu
low = middle + 1➡️ Le mot vient après : écarter la première moitié
high = middle - 1⬅️ Le mot vient avant : écarter la seconde moitié
Chaque comparaison divise par deux ce qui reste, si bien que même une liste énorme demande peu d'étapes.
En une phrase

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

  1. low et high délimitent la partie de la liste qui peut encore contenir la cible.
  2. middle = (low + high) // 2 choisit l'indice du milieu de cette partie.
  3. Si values[middle] < target, la cible est à droite, donc low = middle + 1 ; sinon high = middle - 1.
  4. while low <= high: s'arrête quand la plage est vide, et la fonction renvoie -1 si elle n'a rien trouvé.
  5. 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 : in ou 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

Exécuter le code →
main.py
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))
Obtenir un bouton Run pour cet exemple

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.

  1. Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
  2. Affichez l’état après chaque étape pour observer l’algorithme en action.
  3. Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Exécuter dans le compilateur Python →

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.

Problème
while low < high:
Correction
while low <= high:

Ne pas avancer au-delà du milieu

Avec low = middle, la boucle peut retomber sans fin sur le même milieu.

Problème
low = middle
Correction
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.

Tous les défis