0Pricing
Coding Interview Prep · Leçon

Recherche binaire classique : gauche, droite, milieu

Implémentez la recherche binaire de manière itérative et récursive, maîtrisez les détails de décalage d’une position aux bornes lo/hi et vérifiez la correction avec des entrées représentant des cas limites.

Recherche binaire classique : gauche, droite, milieu est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.

Pourquoi la recherche binaire est importante

La recherche binaire réduit un parcours linéaire en O(n) à O(log n) en divisant par deux l’espace de recherche à chaque étape. Dans un tableau d’un million d’éléments, un parcours linéaire nécessite jusqu’à 1 000 000 comparaisons, tandis qu’une recherche binaire en nécessite au plus 20. Cette efficacité en fait l’un des algorithmes les plus souvent évalués lors des entretiens de programmation.

L’idée fondamentale est qu’un tableau trié permet de décider, après une seule comparaison, quelle moitié des données restantes éliminer entièrement.

Le cadre gauche, milieu, droite

La recherche binaire utilise trois pointeurs d’indices : lo (borne gauche), hi (borne droite) et mid (point médian). À chaque itération, vous calculez mid = (lo + hi) // 2 et comparez la cible à arr[mid]. Si la cible est plus petite, déplacez hi = mid - 1 ; si elle est plus grande, déplacez lo = mid + 1 ; si elle est égale, vous l’avez trouvée.

La boucle continue tant que lo <= hi. Lorsqu’elle se termine sans trouver la cible, renvoyez -1.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search([1, 3, 5, 7, 9, 11], 7))  # 3
print(binary_search([1, 3, 5, 7, 9, 11], 6))  # -1

Éviter le dépassement d’entier dans mid

L’expression mid = (lo + hi) // 2 peut provoquer un dépassement d’entier dans les langages utilisant des entiers de largeur fixe (Java, C++). Les entiers de Python ont une précision arbitraire, donc aucun dépassement ne se produit, mais les recruteurs s’attendent tout de même à ce que vous connaissiez l’alternative sûre : mid = lo + (hi - lo) // 2.

Cette forme calcule le même point médian, mais ajoute seulement la moitié de la distance à lo au lieu d’additionner d’abord les deux pointeurs. Mentionner ce point lors d’un entretien montre que vous êtes conscient des contraintes de bas niveau.

# Safe mid calculation (important in Java/C++, good habit in Python too)
lo, hi = 0, 1_000_000_000
mid_unsafe = (lo + hi) // 2   # fine in Python
mid_safe   = lo + (hi - lo) // 2  # same result, no overflow risk
print(mid_unsafe == mid_safe)  # True

Bornes inclusives ou exclusives

L’un des aspects les plus délicats de la recherche binaire consiste à choisir si hi pointe vers le dernier indice valide (borne inclusive, hi = len(arr) - 1) ou vers l’indice juste après la fin (borne exclusive, hi = len(arr)). Les différentes conventions nécessitent des conditions de boucle et des mises à jour des bornes différentes.

Avec des bornes inclusives, utilisez while lo <= hi et mettez à jour hi = mid - 1. Avec des bornes exclusives, utilisez while lo < hi et mettez à jour hi = mid. Mélanger ces conventions est la principale source d’erreurs dans les implémentations de recherche binaire.

# Exclusive hi variant — useful for bisect-style lower-bound
def search_exclusive(arr, target):
    lo, hi = 0, len(arr)  # hi is one past last
    while lo < hi:          # strictly less than
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid         # NOT mid - 1
    return lo if lo < len(arr) and arr[lo] == target else -1

print(search_exclusive([2, 4, 6, 8, 10], 6))  # 2

Recherche binaire récursive

La recherche binaire peut être écrite de manière récursive en transmettant les bornes lo et hi mises à jour à travers la pile d’appels. Chaque appel récursif réduit l’espace de recherche de moitié, la profondeur est donc de O(log n). Le cas de base est atteint lorsque lo > hi (cible introuvable) ou lorsque arr[mid] == target (cible trouvée).

La version itérative est privilégiée dans le code de production, car elle évite la surcharge des cadres de pile, mais la version récursive communique plus clairement la structure diviser pour régner sur un tableau blanc.

def binary_search_rec(arr, target, lo, hi):
    if lo > hi:
        return -1
    mid = lo + (hi - lo) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_rec(arr, target, mid + 1, hi)
    else:
        return binary_search_rec(arr, target, lo, mid - 1)

arr = [1, 3, 5, 7, 9, 11]
print(binary_search_rec(arr, 9, 0, len(arr) - 1))  # 4

Cas limites : tableau vide, élément unique

Une recherche binaire robuste doit gérer les cas limites sans provoquer d’erreur. Les trois plus courants sont : un tableau vide (la boucle ne s’exécute jamais et -1 est renvoyé correctement), un tableau à un seul élément (mid est égal à lo et à hi, une seule comparaison suffit) et des cibles hors intervalle (lo finit par dépasser hi et -1 est renvoyé).

Vérifiez toujours votre implémentation avec ces entrées avant de passer aux questions complémentaires d’un entretien.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search([], 5))       # -1  (empty)
print(binary_search([7], 7))      # 0   (single, found)
print(binary_search([7], 3))      # -1  (single, not found)
print(binary_search([1,3,5], 0))  # -1  (below range)
print(binary_search([1,3,5], 9))  # -1  (above range)

Complexité temporelle et spatiale

La recherche binaire a une complexité temporelle de O(log n), car chaque comparaison divise l’espace de recherche par deux. Après k comparaisons, l’espace restant est n/2^k ; la recherche se termine lorsqu’il atteint 1, donc k = log₂ n.

La complexité spatiale est de O(1) pour la version itérative (seulement trois variables entières) et de O(log n) pour la version récursive, en raison de la profondeur de la pile d’appels. Lors d’un entretien, indiquez toujours les deux complexités et préférez la forme itérative lorsque la mémoire est limitée.

import math

for n in [10, 100, 1000, 1_000_000, 1_000_000_000]:
    steps = math.ceil(math.log2(n + 1))
    print(f'n={n:>12,}  max comparisons={steps}')

Recherche d’une correspondance exacte ou d’une frontière

La recherche binaire classique renvoie n’importe quel indice où la cible existe. Mais de nombreux problèmes d’entretien demandent la première ou la dernière occurrence d’une cible. Dans ces cas, vous devez continuer à chercher même après avoir trouvé une correspondance : au lieu de renvoyer immédiatement le résultat, resserrez la borne et poursuivez la recherche.

Pour rechercher la première occurrence, après avoir trouvé arr[mid] == target, enregistrez mid comme candidat et définissez hi = mid - 1. Pour la dernière occurrence, définissez lo = mid + 1.

def first_occurrence(arr, target):
    lo, hi, result = 0, len(arr) - 1, -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            result = mid
            hi = mid - 1   # keep searching left
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return result

print(first_occurrence([1, 2, 2, 2, 3], 2))  # 1

Utiliser le module bisect de Python

La bibliothèque standard de Python fournit bisect.bisect_left(arr, x) et bisect.bisect_right(arr, x) pour effectuer une recherche binaire prête pour la production. bisect_left renvoie l’indice le plus à gauche où x peut être inséré tout en conservant le tableau trié, ce qui revient à trouver la première position où arr[i] >= x.

Les recruteurs peuvent vous autoriser à utiliser bisect ; demandez-leur toujours confirmation au préalable. Il est néanmoins essentiel de savoir comment ce module fonctionne en interne (il s’agit d’une recherche binaire en O(log n)).

import bisect

arr = [1, 2, 2, 2, 3, 5]

print(bisect.bisect_left(arr, 2))   # 1  (first 2)
print(bisect.bisect_right(arr, 2))  # 4  (after last 2)

# Check if target exists
target = 3
idx = bisect.bisect_left(arr, target)
print(idx < len(arr) and arr[idx] == target)  # True

Pièges courants de la recherche binaire

Trois erreurs sont à l’origine de la plupart des problèmes de recherche binaire en entretien. Premièrement, une condition de boucle incorrecte : utiliser < au lieu de <= avec des bornes inclusives fait ignorer le dernier élément restant. Deuxièmement, une mise à jour incorrecte des bornes : oublier le +1 ou le -1 crée une boucle infinie lorsque lo == hi. Troisièmement, travailler sur un tableau non trié : la recherche binaire n’est correcte que sur des données triées.

Avant d’écrire une recherche binaire, dites à voix haute : « Le tableau est trié, mes bornes sont inclusives et ma boucle s’exécute tant que lo <= hi. »

# BUG: infinite loop when lo == hi because hi = mid never moves past lo
def buggy(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:              # should be lo <= hi for exact-match
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid            # stops, but never returns mid when found
    return lo if arr[lo] == target else -1

print(buggy([1, 3, 5, 7], 7))  # 3 (works here by luck)
print(buggy([1, 3, 5, 7], 1))  # 0 (correct)
print(buggy([1, 3, 5, 7], 4))  # -1 (correct)

Conseils d’entretien pour la recherche binaire

Lorsque vous voyez un problème portant sur un tableau trié, une fonction strictement croissante ou un espace de recherche qui peut être divisé par deux, pensez immédiatement à la recherche binaire. Lors d’un entretien, expliquez votre raisonnement : « Comme le tableau est trié, je peux éliminer la moitié des éléments à chaque comparaison, ce qui donne O(log n). »

Vérifiez toujours votre solution avec au moins trois entrées : une valeur au début, une valeur à la fin et une valeur absente. Indiquer spontanément la complexité — « temps O(log n), espace O(1) » — avant qu’on vous le demande montre que vous maîtrisez les fondamentaux.

Vérification rapide

Vérifiez votre compréhension des concepts de Structures de données et algorithmes — préparation aux entretiens de programmation abordés dans cette leçon.

Récapitulatif de la leçon

Dans cette leçon, vous avez appris que : la recherche binaire divise l’espace de recherche par deux à chaque étape, pour une complexité temporelle de O(log n) ; la convention des bornes inclusives utilise lo <= hi, avec les mises à jour lo = mid+1 et hi = mid-1 ; et pour trouver la première ou la dernière occurrence, vous poursuivez la recherche après une correspondance au lieu de renvoyer immédiatement le résultat. La prochaine étape consiste à découvrir comment étendre la recherche binaire aux tableaux pivotés et non triés.

Questions Fréquemment Posées

La leçon « Recherche binaire classique : gauche, droite, milieu » est-elle gratuite ?

Oui — le texte complet de « Recherche binaire classique : gauche, droite, milieu » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Recherche binaire classique : gauche, droite, milieu » ?

Implémentez la recherche binaire de manière itérative et récursive, maîtrisez les détails de décalage d’une position aux bornes lo/hi et vérifiez la correction avec des entrées représentant des cas l… Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?

Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.

Combien de temps prend la leçon « Recherche binaire classique : gauche, droite, milieu » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?

Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. Recherche binaire classique : gauche, droite, milieu
  2. Recherche binaire dans des tableaux pivotés et non triés
  3. Borne inférieure et borne supérieure
  4. Recherche binaire dans l’espace des réponses
← Retour à Coding Interview Prep