First True: binäre Suche nach einem Prädikat
Suchen Sie eine monotone Ja-Nein-Grenze
First True: binäre Suche nach einem Prädikat ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 3 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.
Eine Ja/Nein-Grenze suchen
Viele Probleme verbergen ein monotones Prädikat: zuerst false, dann für immer true. Mit binärer Suche können Sie dieses erste true auch ohne sortiertes Array finden.
# FFFFTTTT -> find first TWas monoton bedeutet
Ein Prädikat ist monoton, wenn es nach dem Wechsel zu true true bleibt. Genau diese Eigenschaft ermöglicht die binäre Suche nach der Grenze.
def ok(x):
return x * x >= targetDen Lösungsraum festlegen
Wählen Sie einen Bereich, der die Grenze sicher enthält. Setzen Sie low auf den kleinsten Kandidaten und high auf einen Wert, für den ok sicher true ist.
low, high = 0, 10**9Die Mitte prüfen
Nehmen Sie mid und rufen Sie ok(mid) auf. Das boolesche Ergebnis zeigt Ihnen, welche Hälfte beibehalten wird – genau wie beim Vergleich eines Werts in der gewöhnlichen binären Suche.
mid = (low + high) // 2
if ok(mid):
...True bedeutet: Vielleicht kleiner
Wenn ok(mid) true ist, ist mid eine gültige Antwort, aber möglicherweise funktioniert auch eine kleinere. Behalten Sie mid bei, indem Sie high = mid statt mid - 1 setzen.
if ok(mid):
high = midFalse bedeutet: Höher suchen
Wenn ok(mid) false ist, liegt die Grenze oberhalb von mid. Verwerfen Sie mid und alles darunter mit low = mid + 1.
else:
low = mid + 1Schleife, solange Low unter High liegt
Verwenden Sie while low < high, nicht kleiner-gleich. Die beiden Zeiger laufen beim ersten true-Index zusammen, woraufhin die Schleife endet.
while low < high:
mid = (low + high) // 2Die Antwort ist Low
Wenn die Schleife endet, sind low und high gleich und zeigen beide auf den ersten true-Wert. Geben Sie low als gesuchte Grenze zurück.
return low # first x where ok(x)Warum high = mid funktioniert
Da mid die Antwort sein kann, dürfen Sie es nicht überspringen. Mit high = mid bleibt es im Bereich, während dieser trotzdem kleiner wird, sodass der Fortschritt garantiert ist.
high = mid # mid stays a candidateBeispiel: Ganzzahlige Quadratwurzel
Um das größte x mit x*x höchstens n zu finden, suchen Sie das erste true für x*x > n und gehen dann um eins zurück. Dieses Muster lässt sich wiederverwenden.
def ok(x):
return x * x > n
# answer is found_index - 1Eine Vorlage, viele Probleme
Diese first-true-Vorlage löst unzählige Aufgaben: den kleinsten zulässigen Wert, den am weitesten links liegenden Index oder die kleinste Kapazität. Lernen Sie sie einmal und verwenden Sie sie überall wieder.
# low<high, ok->high=mid, else low=mid+1Kurzer Check
Bestimmen Sie den Schritt, der den Kandidaten im Suchraum hält.
Zusammenfassung: Erstes True gefunden
Sie können jetzt ein Problem in ein monotones Prädikat umwandeln und die Grenze per binärer Suche finden. high = mid zusammen mit while low < high ist das sichere Muster. 🧭
Häufig gestellte Fragen
Ist die Lektion „First True: binäre Suche nach einem Prädikat“ kostenlos?
Ja — der vollständige Text von „First True: binäre Suche nach einem Prädikat“ 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 „First True: binäre Suche nach einem Prädikat“?
Suchen Sie eine monotone Ja-Nein-Grenze 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 3 von 4.
Wie lange dauert die Lektion „First True: binäre Suche nach einem Prädikat“?
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