Klassische binäre Suche ohne Fehler
Beherrschen Sie die Schleife mit low, high und mid
Klassische binäre Suche ohne Fehler 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.
Den Suchraum halbieren
Binäre Suche findet einen Wert in einer sortierten Liste, indem sie den Bereich in jedem Schritt halbiert. Dadurch wird aus einem langsamen O(n)-Durchlauf eine schnelle Suche in O(log n).
a = [1, 3, 5, 7, 9] # must be sortedSortiert ist die einzige Voraussetzung
Binäre Suche funktioniert nur mit sortierten Daten. Ist die Liste ungeordnet, sortieren Sie sie zuerst, andernfalls ist das Ergebnis bedeutungslos und falsch.
a.sort() # ascending order requiredZwei Grenzen
Beginnen Sie mit zwei Zeigern: low bei Index 0 und high beim letzten Index. Falls das Ziel vorhanden ist, liegt es immer zwischen diesen beiden Grenzen.
low, high = 0, len(a) - 1Die Mitte sicher bestimmen
Berechnen Sie mid als low + (high - low) // 2. In Python ist ein Überlauf kein Problem, aber diese Form ist überall eine sichere Gewohnheit.
mid = low + (high - low) // 2Drei Fälle
Vergleichen Sie a[mid] mit dem Ziel. Entweder haben Sie es gefunden, es ist zu klein oder es ist zu groß. Jeder Fall verkleinert den Bereich auf eine andere Weise.
if a[mid] == target:
return midZu klein, nach rechts
Wenn a[mid] kleiner als das Ziel ist, muss die Antwort rechts liegen. Verschieben Sie low auf mid + 1 und verwerfen Sie die linke Hälfte.
elif a[mid] < target:
low = mid + 1Zu groß, nach links
Wenn a[mid] größer als das Ziel ist, suchen Sie in der linken Hälfte. Verschieben Sie high auf mid - 1, damit Sie mid nicht erneut prüfen.
else:
high = mid - 1Die Schleifenbedingung
Fahren Sie solange low kleiner oder gleich high ist fort. Sobald sich die beiden überschneiden, ist der Bereich leer und das Ziel nicht vorhanden.
while low <= high:
mid = low + (high - low) // 2Nicht gefunden melden
Endet die Schleife ohne Treffer, ist der Wert nicht vorhanden. Geben Sie konventionsgemäß -1 zurück, damit Aufrufer Erfolg und Fehlschlag unterscheiden können.
return -1 # target not in listDie Off-by-one-Falle
Der klassische Fehler besteht darin, das +1 oder -1 beim Verschieben eines Zeigers zu vergessen. Lassen Sie es weg, wird mid endlos erneut geprüft und es entsteht eine Endlosschleife.
low = mid + 1 # not low = midVerwenden Sie die Bibliothek, wenn möglich
Für eine einfache Enthaltenseinsprüfung bietet Pythons Modul bisect bereits eine fehlerfreie Suche. Schreiben Sie die Schleife nur selbst, wenn Sie eine eigene Logik benötigen.
import bisect
i = bisect.bisect_left(a, target)Kurzer Check
Überlegen Sie, wodurch die Schleife korrekt begrenzt bleibt.
Zusammenfassung: Fehlerfrei suchen
Sie können jetzt low und high setzen, mid sicher berechnen, die rechte Seite verkleinern und die Off-by-one-Falle vermeiden. Die logarithmische Suche steht Ihnen zur Verfügung. 🎯
Häufig gestellte Fragen
Ist die Lektion „Klassische binäre Suche ohne Fehler“ kostenlos?
Ja — der vollständige Text von „Klassische binäre Suche ohne Fehler“ 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 ohne Fehler“?
Beherrschen Sie die Schleife mit low, high und mid 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 ohne Fehler“?
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 ohne Fehler
- bisect_left und bisect_right
- First True: binäre Suche nach einem Prädikat
- Binäre Suche nach der Antwort