ConsigneImplé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.
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)) # → 3gauche / droite bornes de la zone encore à explorer (inclusives)// (division entière) on veut un index entierreturn -1 convention pour "non trouvé" (les index valides sont ≥ 0)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.
Envie d'aller plus loin ? Découvrez nos formations certifiées Bac+2 à Bac+5 →