Exercice 44 / 100
Recherche binaire
Implémentez la recherche binaire dans une liste triée
La recherche binaire trouve la position d'un élément dans une liste triée en O(log n) — beaucoup plus rapide qu'une recherche linéaire en O(n).
Principe : à chaque étape, on regarde l'élément du milieu.
- si c'est la cible → trouvé
- si cible plus petite → chercher dans la moitié gauche
- si cible plus grande → chercher dans la moitié droite
À chaque comparaison, on divise l'espace de recherche par 2. Pour 1 million d'éléments : ~ 20 comparaisons (log₂(10⁶) ≈ 20).
prérequis absolu : la liste doit être triée. Sinon, l'algo donne des résultats faux.
Implémentation itérative
def recherche_binaire(arr, cible):
gauche, droite = 0, len(arr) - 1
while gauche <= droite:
milieu = (gauche + droite) // 2
if arr[milieu] == cible:
return milieu
elif arr[milieu] < cible:
gauche = milieu + 1 # chercher à droite
else:
droite = milieu - 1 # chercher à gauche
return -1 # non trouvéprint(recherche_binaire([1,3,5,7,9,11,13], 7)) # → 3Lecture détaillée
gauche / droite bornes de la zone encore à explorer (inclusives)- milieu
- élément central
// (division entière) on veut un index entier
return -1 convention pour "non trouvé" (les index valides sont ≥ 0)En pratique (Python)
La lib standard fournit déjà tout :
from bisect import bisect_left, insortidx = bisect_left(arr, 7) # position de 7 (ou d'insertion si absent)
insort(arr, 6) # insère 6 au bon endroitRègle : connaître la recherche binaire est essentiel (entretiens, structures d'index, base de données). En prod, utilise bisect.