Commencer→
Retour au cours

backend / algorithmes-structures-donnees

Recherche linéaire et binaire

Leçon 51 exercice

Explication

Ce que vous allez apprendre

  • Comparer recherche linéaire (O(n)) et recherche binaire (O(log n)) et savoir laquelle choisir selon le contexte
  • Formuler l'invariant qui garantit la correction de la recherche binaire à chaque itération
  • Expliquer pourquoi le tri préalable est la condition indispensable de la recherche binaire
  • Évaluer le compromis entre coût de tri et gain de recherche selon la fréquence des lectures face aux mises à jour
  • Généraliser la recherche binaire à une fonction monotone quelconque (par exemple trouver une racine carrée entière)

Dans quel contexte ?

Le moteur de recherche interne d'une entreprise doit vérifier si un identifiant de commande existe parmi 2 millions d'identifiants triés, plusieurs milliers de fois par seconde. Une recherche linéaire parcourrait en moyenne un million de commandes par requête ; une recherche binaire n'en examine que log2(2 000 000), soit environ 21. C'est exactement la différence entre une API qui répond en microsecondes et une API qui met des secondes à répondre sous charge.

D'abord, la méthode la plus simple : tout regarder

Chercher un mot dans un tas de papiers non triés oblige à tout regarder un par un : c'est la recherche linéaire, O(n), simple et universelle mais qui ne profite d'aucune structure.

Prérequis

Cette leçon s'appuie directement sur la notation Big O vue en leçon 1 : gardez en tête que O(n) et O(log n) ne sont pas juste "plus lent" ou "plus rapide", mais deux façons radicalement différentes de réagir à la croissance des données.

Une meilleure méthode existe, mais à une condition

Chercher un mot dans un dictionnaire papier ne se fait jamais page par page : on l'ouvre au milieu, on compare, et on élimine instantanément la moitié des pages restantes. Mais cette astuce ne fonctionne que parce que le dictionnaire est déjà trié par ordre alphabétique.

CritèreRecherche linéaireRecherche binaire
ComplexitéO(n)O(log n)
Prérequis sur les donnéesAucunDonnées déjà triées
Cas d'usage typiquePetite liste ou données non triéesGrand volume, lectures fréquentes
Coût cachéAucunCoût du tri à maintenir à jour

Étape 1 : l'invariant qui rend la méthode correcte

À chaque étape de la recherche binaire, l'algorithme maintient une garantie simple : si la cible existe dans le tableau, elle se trouve forcément dans l'intervalle actuellement considéré. En comparant l'élément du milieu à la cible, on élimine avec certitude toute une moitié de cet intervalle.

Piège fréquent

L'erreur classique de recherche binaire est l'erreur "off-by-one" sur les bornes : écrire milieu = (gauche + droite) // 2 puis oublier de faire gauche = milieu + 1 (et pas milieu) après une comparaison peut créer une boucle infinie. Vérifiez toujours que l'intervalle [gauche, droite] rétrécit strictement à chaque itération.

Pourquoi ça donne du log n

C'est cette élimination systématique de la moitié restante qui donne le O(log n) : chaque comparaison divise l'espace de recherche par deux, donc il en faut environ log2(n) pour l'épuiser complètement.

Le prix à payer pour cette rapidité

La recherche binaire n'est valable que sur des données déjà triées. Si les données changent constamment, maintenir le tri peut coûter plus cher que le gain apporté par la recherche elle-même, un compromis à évaluer selon le nombre de recherches face au nombre de mises à jour.

Pour aller plus loin : au-delà d'un simple tableau

L'idée clé, diviser l'espace des réponses possibles par deux à chaque étape, se généralise à toute fonction monotone, pas seulement à un tableau trié. Trouver une racine carrée entière utilise exactement le même squelette logique, appliqué à un espace de réponses plutôt qu'à un tableau.

Vers la suite

Une fois qu'on sait chercher efficacement dans des données triées, la question naturelle suivante est : comment trie-t-on ces données en premier lieu ? C'est le sujet des deux prochaines leçons, sur les algorithmes de tri.

Commandes & code

Recherche linéaire et binaire

python
# --- Recherche linéaire : O(n), fonctionne sur donnée NON triée ---
def recherche_lineaire(tableau: list, cible) -> int:
    for i, valeur in enumerate(tableau):
        if valeur == cible:
            return i
    return -1

# --- Recherche binaire itérative : O(log n), EXIGE une donnée triée ---
def recherche_binaire(tableau: list[int], cible: int) -> int:
    gauche, droite = 0, len(tableau) - 1
    while gauche <= droite:
        milieu = gauche + (droite - gauche) // 2   # évite un overflow sur d'autres langages
        if tableau[milieu] == cible:
            return milieu
        elif tableau[milieu] < cible:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return -1

# --- Recherche binaire récursive : équivalente, mais O(log n) en espace (pile d'appels) ---
def recherche_binaire_recursive(tableau: list[int], cible: int, gauche: int = 0, droite: int | None = None) -> int:
    if droite is None:
        droite = len(tableau) - 1
    if gauche > droite:
        return -1
    milieu = gauche + (droite - gauche) // 2
    if tableau[milieu] == cible:
        return milieu
    elif tableau[milieu] < cible:
        return recherche_binaire_recursive(tableau, cible, milieu + 1, droite)
    else:
        return recherche_binaire_recursive(tableau, cible, gauche, milieu - 1)

# --- Borne inférieure / supérieure (bisect) : trouver la position d'insertion ---
import bisect

def premiere_occurrence(tableau: list[int], cible: int) -> int:
    # O(log n) : trouve la PREMIÈRE position où cible pourrait apparaître
    i = bisect.bisect_left(tableau, cible)
    if i < len(tableau) and tableau[i] == cible:
        return i
    return -1

def compter_occurrences(tableau: list[int], cible: int) -> int:
    # O(log n) : compte les occurrences dans un tableau trié sans le parcourir entièrement
    gauche = bisect.bisect_left(tableau, cible)
    droite = bisect.bisect_right(tableau, cible)
    return droite - gauche

# --- Recherche binaire sur une fonction monotone (pattern avancé) ---
def racine_carree_entiere(n: int) -> int:
    # trouve floor(sqrt(n)) par recherche binaire sur l'espace des réponses possibles
    if n < 2:
        return n
    gauche, droite = 1, n // 2
    resultat = 1
    while gauche <= droite:
        milieu = gauche + (droite - gauche) // 2
        if milieu * milieu <= n:
            resultat = milieu           # candidat valide, on cherche potentiellement mieux
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return resultat

assert racine_carree_entiere(26) == 5   # 5*5=25 <= 26 < 36=6*6

# --- Recherche dans un tableau tourné (rotated sorted array) : entretien classique ---
def recherche_tableau_tourne(tableau: list[int], cible: int) -> int:
    gauche, droite = 0, len(tableau) - 1
    while gauche <= droite:
        milieu = gauche + (droite - gauche) // 2
        if tableau[milieu] == cible:
            return milieu
        if tableau[gauche] <= tableau[milieu]:      # la moitié gauche est triée
            if tableau[gauche] <= cible < tableau[milieu]:
                droite = milieu - 1
            else:
                gauche = milieu + 1
        else:                                        # la moitié droite est triée
            if tableau[milieu] < cible <= tableau[droite]:
                gauche = milieu + 1
            else:
                droite = milieu - 1
    return -1

assert recherche_tableau_tourne([4, 5, 6, 7, 0, 1, 2], 0) == 4

Résumé

  • Recherche linéaire O(n) : aucune contrainte sur les données, toujours applicable.
  • Recherche binaire O(log n) : exige des données triées, divise l'espace de recherche par 2 à chaque étape.
  • Le module bisect fournit des primitives O(log n) prêtes à l'emploi (position d'insertion, comptage).
  • La recherche binaire s'applique aussi sur l'espace des réponses (ex: racine carrée) tant que la fonction testée est monotone.

Exercices pratiques

1 disponible
1

Mission : retrouver une commande dans un journal tourné

Objectif : Adapter la recherche binaire à un tableau trié mais pivoté, et justifier chaque choix de conception.

Contexte

Le système de commandes d'une boutique en ligne stocke ses identifiants dans un tableau trié par ordre croissant, mais un redémarrage récent a fait pivoter le tableau en mémoire : [4, 5, 6, 7, 0, 1, 2] par exemple, où la partie triée continue mais "recommence" quelque part au milieu. Une recherche binaire classique appliquée telle quelle donnerait des résultats incohérents sur ce tableau.

Tu dois d'abord comprendre pourquoi, puis retrouver ou adapter l'algorithme adapté à ce cas.

Résoudre l’exercice →