Klassische binäre Suche: links, rechts, Mitte
Implementieren Sie die binäre Suche iterativ und rekursiv, beherrschen Sie die Off-by-one-Details der lo/hi-Grenzen und überprüfen Sie die Korrektheit mit Randfall-Eingaben.
Klassische binäre Suche: links, rechts, Mitte ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Warum binäre Suche wichtig ist
Binäre Suche reduziert einen linearen Scan mit O(n) auf O(log n), indem sie den Suchbereich in jedem Schritt halbiert. In einem Array mit einer Million Elementen benötigt ein linearer Scan bis zu 1.000.000 Vergleiche, die binäre Suche dagegen höchstens 20. Diese Effizienz macht sie zu einem der Algorithmen, die in Coding-Interviews am häufigsten getestet werden.
Die zentrale Erkenntnis ist, dass Sie bei einem sortierten Array nach einem einzigen Vergleich entscheiden können, welche Hälfte der verbleibenden Daten vollständig verworfen werden kann.
Das Schema mit Left, Mid und Right
Bei der binären Suche werden drei Zeiger auf Array-Indizes verwendet: lo (linke Grenze), hi (rechte Grenze) und mid (Mittelpunkt). In jeder Iteration berechnen Sie mid = (lo + hi) // 2 und vergleichen das Ziel mit arr[mid]. Ist das Ziel kleiner, setzen Sie hi = mid - 1; ist es größer, setzen Sie lo = mid + 1; bei Gleichheit haben Sie es gefunden.
Die Schleife läuft weiter, solange lo <= hi gilt. Wird die Schleife beendet, ohne das Ziel zu finden, geben Sie -1 zurück.
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)) # -1Ganzzahlüberlauf bei Mid vermeiden
Der Ausdruck mid = (lo + hi) // 2 kann in Sprachen mit Ganzzahlen fester Breite (Java, C++) einen Ganzzahlüberlauf verursachen. Python-Ganzzahlen haben beliebige Genauigkeit, daher tritt dort nie ein Überlauf auf. In Interviews wird jedoch erwartet, dass Sie die sichere Alternative kennen: mid = lo + (hi - lo) // 2.
Diese Form berechnet denselben Mittelpunkt, addiert jedoch nur die halbe Distanz zu lo, anstatt zunächst beide Zeiger zu summieren. Wenn Sie dies in einem Interview erwähnen, zeigen Sie, dass Sie sich der Besonderheiten auf niedriger Ebene bewusst sind.
# 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) # TrueInklusive und exklusive Grenzen
Zu den schwierigsten Aspekten der binären Suche gehört die Entscheidung, ob hi auf den letzten gültigen Index zeigt (inklusive, hi = len(arr) - 1) oder auf die Position nach dem Ende (exklusive, hi = len(arr)). Unterschiedliche Konventionen erfordern unterschiedliche Schleifenbedingungen und Anpassungen der Grenzen.
Bei inklusiven Grenzen verwenden Sie while lo <= hi und aktualisieren hi = mid - 1. Bei exklusiven Grenzen verwenden Sie while lo < hi und aktualisieren hi = mid. Das Vermischen dieser Konventionen ist die häufigste Fehlerquelle bei Implementierungen der binären Suche.
# 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)) # 2Rekursive binäre Suche
Die binäre Suche kann rekursiv implementiert werden, indem aktualisierte Grenzen für lo und hi über den Aufruf-Stack weitergegeben werden. Jeder rekursive Aufruf halbiert den Suchbereich, daher beträgt die Rekursionstiefe O(log n). Der Basisfall tritt ein, wenn lo > hi gilt (nicht gefunden) oder arr[mid] == target gilt (gefunden).
In Produktionscode wird die iterative Variante bevorzugt, da sie den Overhead von Stack-Frames vermeidet. Die rekursive Variante vermittelt jedoch die Divide-and-Conquer-Struktur am Whiteboard klarer.
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)) # 4Sonderfälle: leeres Array, einzelnes Element
Eine robuste binäre Suche muss Sonderfälle verarbeiten, ohne abzustürzen. Die drei häufigsten sind: ein leeres Array (die Schleife wird nie ausgeführt und korrekt -1 zurückgegeben), ein Array mit einem einzelnen Element (mid ist gleich lo und gleich hi, ein Vergleich genügt) und Zielwerte außerhalb des Bereichs (lo wird schließlich größer als hi und -1 wird zurückgegeben).
Überprüfen Sie Ihre Implementierung immer mit diesen Eingaben, bevor Sie in einem Interview zu weiterführenden Fragen übergehen.
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)Zeit- und Speicherkomplexität
Die binäre Suche hat eine Zeitkomplexität von O(log n), da jeder Vergleich den Suchbereich halbiert. Nach k Vergleichen verbleibt ein Bereich der Größe n/2^k; die Suche endet, wenn dieser die Größe 1 erreicht, also bei k = log₂ n.
Die Speicherkomplexität beträgt bei der iterativen Variante O(1) (nur drei ganzzahlige Variablen) und bei der rekursiven Variante aufgrund der Tiefe des Aufruf-Stacks O(log n). Geben Sie in einem Interview immer beide Komplexitäten an und bevorzugen Sie die iterative Form, wenn der Speicher begrenzt ist.
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}')Nach exakter Übereinstimmung oder einer Grenze suchen
Die klassische binäre Suche gibt einen beliebigen Index zurück, an dem das Ziel vorhanden ist. Viele Interviewaufgaben verlangen jedoch das erste oder letzte Vorkommen eines Zielwerts. In diesen Fällen müssen Sie auch nach einem Treffer weitersuchen – statt sofort zurückzukehren, schränken Sie die Grenze ein und suchen weiter.
Wenn Sie nach dem ersten Vorkommen suchen, speichern Sie nach arr[mid] == target mid als möglichen Treffer und setzen Sie hi = mid - 1. Für das letzte Vorkommen setzen Sie 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)) # 1Pythons bisect-Modul verwenden
Pythons Standardbibliothek stellt mit bisect.bisect_left(arr, x) und bisect.bisect_right(arr, x) produktionsreife Funktionen für die binäre Suche bereit. bisect_left gibt den am weitesten links liegenden Index zurück, an dem x eingefügt werden kann, ohne die Sortierung des Arrays zu ändern. Damit wird effektiv die erste Position gefunden, an der arr[i] >= x gilt.
Interviewende erlauben Ihnen möglicherweise, bisect zu verwenden; klären Sie dies immer vorher. Es bleibt jedoch unerlässlich zu wissen, wie das Modul intern funktioniert (es handelt sich um eine binäre Suche mit 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) # TrueHäufige Fallstricke bei der binären Suche
Drei Fehler verursachen in Interviews die meisten Probleme bei der binären Suche. Erstens eine falsche Schleifenbedingung: Wenn Sie bei inklusiven Grenzen < statt <= verwenden, wird das letzte verbleibende Element übersprungen. Zweitens eine fehlerhafte Anpassung der Grenze: Wenn Sie +1 oder -1 vergessen, entsteht bei lo == hi eine Endlosschleife. Drittens die Verwendung eines unsortierten Arrays: Binäre Suche ist nur bei sortierten Daten korrekt.
Sagen Sie vor jeder Implementierung einer binären Suche laut: „Das Array ist sortiert, meine Grenzen sind inklusiv, und meine Schleife läuft, solange lo <= hi gilt.“
# 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)Interviewtipps für die binäre Suche
Wenn Sie auf ein Problem mit einem sortierten Array, einer monoton steigenden Funktion oder einem Suchbereich stoßen, der halbiert werden kann, ziehen Sie sofort die binäre Suche in Betracht. Erläutern Sie in einem Interview Ihre Überlegungen: „Da das Array sortiert ist, kann ich pro Vergleich die Hälfte der Elemente verwerfen, was O(log n) ergibt.“
Überprüfen Sie Ihre Lösung immer mit mindestens drei Eingaben: einem Wert am Anfang, einem Wert am Ende und einem nicht vorhandenen Wert. Wenn Sie die Komplexität proaktiv angeben – „Zeit O(log n), Speicher O(1)“ –, bevor Sie danach gefragt werden, zeigen Sie solide Grundlagen.
Kurzer Test
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.
Lektionszusammenfassung
In dieser Lektion haben Sie Folgendes gelernt: Die binäre Suche halbiert den Suchbereich in jedem Schritt und benötigt daher O(log n) Zeit, die Konvention mit inklusiven Grenzen verwendet lo <= hi sowie die Aktualisierungen lo = mid+1 und hi = mid-1, und um erste oder letzte Vorkommen zu finden, suchen Sie nach einem Treffer weiter, statt sofort zurückzukehren. Als Nächstes untersuchen Sie, wie sich die binäre Suche auf rotierte und unsortierte Arrays erweitern lässt.
Häufig gestellte Fragen
Ist die Lektion „Klassische binäre Suche: links, rechts, Mitte“ kostenlos?
Ja — der vollständige Text von „Klassische binäre Suche: links, rechts, Mitte“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Klassische binäre Suche: links, rechts, Mitte“?
Implementieren Sie die binäre Suche iterativ und rekursiv, beherrschen Sie die Off-by-one-Details der lo/hi-Grenzen und überprüfen Sie die Korrektheit mit Randfall-Eingaben. Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.
Wie lange dauert die Lektion „Klassische binäre Suche: links, rechts, Mitte“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Klassische binäre Suche: links, rechts, Mitte
- Binäre Suche in rotierten und unsortierten Arrays
- Untere und obere Grenze
- Binäre Suche im Lösungsraum