Recherche binaire classique sans erreurs
Maîtriser la boucle low, high et mid
Recherche binaire classique sans erreurs 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.
Réduisez de moitié l’espace de recherche
La recherche binaire trouve une valeur dans une liste triée en divisant la plage par deux à chaque étape. Cela transforme un parcours O(n) lent en recherche O(log n) rapide.
a = [1, 3, 5, 7, 9] # must be sortedLe tri est la règle essentielle
La recherche binaire ne fonctionne que sur des données triées. Si la liste n’est pas ordonnée, triez-la d’abord, sinon le résultat n’aura aucun sens et sera faux.
a.sort() # ascending order requiredDeux bornes
Commencez avec deux pointeurs : low à l’indice 0 et high au dernier indice. La cible, si elle est présente, se trouve toujours entre eux.
low, high = 0, len(a) - 1Calculez le milieu en toute sécurité
Calculez mid avec low + (high - low) // 2. En Python, le dépassement de capacité ne pose pas problème, mais cette forme est une habitude sûre à adopter partout.
mid = low + (high - low) // 2Trois résultats
Comparez a[mid] à la cible. Soit vous l’avez trouvée, soit elle est trop petite, soit elle est trop grande. Chaque cas réduit la plage différemment.
if a[mid] == target:
return midTrop petite, allez à droite
Si a[mid] est inférieur à la cible, la réponse doit se trouver à droite. Déplacez low vers mid + 1 et éliminez la moitié gauche.
elif a[mid] < target:
low = mid + 1Trop grande, allez à gauche
Si a[mid] est supérieur à la cible, recherchez dans la moitié gauche. Déplacez high vers mid - 1 afin de ne jamais réexaminer mid.
else:
high = mid - 1La condition de boucle
Continuez tant que low est inférieur ou égal à high. Lorsqu’ils se croisent, la plage est vide et la cible est absente.
while low <= high:
mid = low + (high - low) // 2Signalez l’absence
Si la boucle se termine sans correspondance, la valeur est absente. Renvoyez -1 par convention afin que le code appelant puisse distinguer la réussite de l’échec.
return -1 # target not in listLe piège du décalage d’un indice
L’erreur classique consiste à oublier le +1 ou -1 lors du déplacement d’un pointeur. Omettez-le, et mid est retesté indéfiniment, ce qui provoque une boucle infinie.
low = mid + 1 # not low = midUtilisez la bibliothèque lorsque c’est possible
Pour un simple test d’appartenance, le module bisect de Python propose déjà une recherche sans bogues. N’écrivez la boucle vous-même que si vous avez besoin d’une logique personnalisée.
import bisect
i = bisect.bisect_left(a, target)Vérification rapide
Réfléchissez à ce qui garantit la correction de la boucle.
Récapitulatif : rechercher sans bogues
Vous savez maintenant définir low et high, calculer mid en toute sécurité, réduire le côté approprié et éviter le piège du décalage d’un indice. La recherche logarithmique est à votre portée. 🎯
Questions Fréquemment Posées
La leçon « Recherche binaire classique sans erreurs » est-elle gratuite ?
Oui — le texte complet de « Recherche binaire classique sans erreurs » 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 sans erreurs » ?
Maîtriser la boucle low, high et mid 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 sans erreurs » ?
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
- Recherche binaire classique sans erreurs
- bisect_left et bisect_right
- Premier True : recherche binaire par prédicat
- Recherche binaire sur la réponse