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 Competitive Programming Academy-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 Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-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) trueDen 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 <= DDie 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) // 2Die 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 + 1Das 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 iterationsMaximieren 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 - 1Antworten 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) / 2Das 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 answerKurzer 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 Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-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 Competitive Programming Academy 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 Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy 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 Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-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