0Pricing
Coding Interview Prep · Lektion

Binäre Suche nach der Antwort

Schätzen Sie das Ergebnis und prüfen Sie seine Machbarkeit

Binäre Suche nach der Antwort ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 4 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.

Raten und anschließend prüfen

Manchmal können Sie die Antwort nicht direkt berechnen, aber Sie können eine Vermutung prüfen. Die binäre Suche nach der Antwort verwandelt schwierige Optimierung in eine einfache Prüfung.

# guess X, ask: is X feasible?

Die entscheidende Eigenschaft

Das funktioniert, wenn die Machbarkeit monoton ist: Wenn ein Wert funktioniert, funktioniert auch jeder größere oder kleinere Wert. Diese Ordnung ist es, die Sie durchsuchen.

# feasible(X) true => feasible(X+1) true

Den Antwortbereich begrenzen

Bestimmen Sie die kleinste und größte mögliche Antwort als low und high. Bei einer minimalen Kapazität ist low ein einzelnes Element und high die Gesamtsumme.

low, high = max(weights), sum(weights)

Die Machbarkeitsprüfung schreiben

Das Herzstück der Methode ist eine can(X)-Funktion, die true zurückgibt, wenn die Vermutung X erreichbar ist. Sie läuft normalerweise in linearer Zeit.

def can(cap):
    # simulate and return True/False
    ...

Beispiel: In D Tagen verschiffen

Bei einer täglichen Kapazität cap füllen Sie die Tage Greedy auf und zählen sie. can(cap) ist true, wenn die Anzahl der Tage innerhalb des Limits D bleibt.

def can(cap):
    days, load = 1, 0
    for w in weights:
        if load + w > cap:
            days += 1; load = 0
        load += w
    return days <= D

Die minimale Kapazität suchen

Gesucht ist das kleinste cap, das die Prüfung besteht. Das ist eine first-true-Suche über Kapazitäten, verwenden Sie daher erneut die Vorlage mit high = mid.

while low < high:
    mid = (low + high) // 2

Die zulässige Hälfte behalten

Wenn can(mid) true ist, könnte auch eine kleinere Kapazität ausreichen, setzen Sie daher high = mid. Andernfalls erhöhen Sie die Untergrenze mit low = mid + 1.

if can(mid):
    high = mid
else:
    low = mid + 1

Das Zeitbudget beachten

Die Gesamtkosten betragen O(check x log range). Eine lineare Prüfung über einen Bereich von einer Milliarde Werten erfordert nur etwa 30 Prüfungen und ist schnell genug für enge Limits.

# log2(1e9) is about 30 iterations

Maximieren statt minimieren

Um den größten zulässigen Wert zu finden, drehen Sie die Logik um: Suchen Sie das letzte true. Erhöhen Sie low, wenn der Wert zulässig ist, und verringern Sie high, wenn er es nicht ist.

if can(mid):
    low = mid
else:
    high = mid - 1

Antworten mit reellen Zahlen

Bei Gleitkommaantworten wiederholen Sie die Schleife beispielsweise 100-mal, statt ein ganzzahliges mid zu verwenden. Jede Runde halbiert das Intervall und erreicht schnell eine sehr hohe Genauigkeit.

for _ in range(100):
    mid = (low + high) / 2

Das Muster erkennen

Formulierungen wie „kleinstes Maximum“, „größtes Minimum“ oder „kleinstes k, das funktioniert“ sind Signale dafür, dass Sie die Antwort per binärer Suche bestimmen sollten. Schulen Sie Ihren Blick dafür.

# 'minimize the maximum' => search answer

Kurzer Check

Entscheiden Sie, wann sich binäre Suche nach der Antwort anwenden lässt.

Zusammenfassung: Die Antwort suchen

Sie können jetzt die Antwort eingrenzen, eine Machbarkeitsprüfung schreiben und per binärer Suche das Minimum oder Maximum finden. Schwierige Probleme werden zu Raten und Prüfen. 🏆

Häufig gestellte Fragen

Ist die Lektion „Binäre Suche nach der Antwort“ kostenlos?

Ja — der vollständige Text von „Binäre Suche nach der Antwort“ 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 „Binäre Suche nach der Antwort“?

Schätzen Sie das Ergebnis und prüfen Sie seine Machbarkeit 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 4 von 4.

Wie lange dauert die Lektion „Binäre Suche nach der Antwort“?

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

  1. Klassische binäre Suche ohne Fehler
  2. bisect_left und bisect_right
  3. First True: binäre Suche nach einem Prädikat
  4. Binäre Suche nach der Antwort
← Zurück zu Coding Interview Prep