Binäre Suche im Lösungsraum
Betrachten Sie einen kontinuierlichen Lösungsbereich als Suchraum, um Probleme wie minimum-time-to-complete-jobs und capacity-to-ship-packages zu lösen.
Binäre Suche im Lösungsraum 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.
Binäre Suche im Lösungsraum
Die meisten kennen die binäre Suche, um einen Wert in einem sortierten Array zu finden. Aber die binäre Suche ist noch leistungsfähiger, wenn sie auf den Raum möglicher Antworten angewendet wird. Statt ein Array zu durchsuchen, durchsuchen Sie einen numerischen Bereich — zum Beispiel: „Wie viele Tage sind mindestens erforderlich, um alle Pakete zu versenden?“ — und verwenden eine Prüffunktion, um zu entscheiden, ob eine mögliche Antwort zulässig ist.
Mit dieser Technik lassen sich viele Optimierungsprobleme von O(n²) oder schlechter auf O(n log(max_answer)) verbessern.
Das Muster für den Lösungsraum
Das Muster besteht aus drei Komponenten. Definieren Sie zunächst den Suchbereich [lo, hi], der alle gültigen Antworten einschließt. Schreiben Sie anschließend eine Machbarkeitsprüfung can_achieve(mid), die True zurückgibt, wenn der Wert mid erreichbar ist. Führen Sie schließlich eine binäre Suche über [lo, hi] durch: Wenn can_achieve(mid) wahr ist, bewegen Sie sich in Richtung einer kleineren (oder größeren) Antwort; andernfalls bewegen Sie sich in die andere Richtung.
Die entscheidende Eigenschaft ist: Die Machbarkeitsfunktion muss monoton sein — sobald eine Antwort machbar ist, sind auch alle Werte jenseits davon machbar (oder alle Werte darunter nicht machbar).
# Generic template
def answer_space_search(lo, hi, is_feasible):
result = hi # or lo, depending on direction
while lo <= hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
result = mid
hi = mid - 1 # try to minimise further
else:
lo = mid + 1
return resultBeispiel: Kapazität für den Paketversand
LeetCode 1011 'Capacity to Ship Packages Within D Days': Bei einer Liste von Gewichten und D Tagen soll die minimale Versandkapazität bestimmt werden, mit der alle Pakete in der vorgegebenen Reihenfolge innerhalb von D Tagen versendet werden können. Die Antwort liegt in [max(weights), sum(weights)]. Eine Kapazität ist zulässig, wenn eine Greedy-Simulation alle Pakete innerhalb von D Tagen unterbringt. Eine Binärsuche über den Kapazitätsbereich liefert eine Laufzeit von O(n log(sum)).
def shipWithinDays(weights, days):
def can_ship(capacity):
needed_days, current_load = 1, 0
for w in weights:
if current_load + w > capacity:
needed_days += 1
current_load = 0
current_load += w
return needed_days <= days
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_ship(mid):
hi = mid # feasible, try smaller
else:
lo = mid + 1 # not feasible, need more capacity
return lo
print(shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5)) # 15
print(shipWithinDays([3,2,2,4,1,4], 3)) # 6Beispiel: Koko isst Bananen
LeetCode 875 'Koko Eating Bananas': Koko kann K Bananen pro Stunde essen; sie möchte H Haufen in genau H Stunden aufessen und dabei K minimieren. Der Suchbereich ist [1, max(piles)]. Die Prüfung: Bei der Rate K beträgt die Gesamtzeit = sum(ceil(pile/K)) Stunden und muss <= H sein. Wir führen eine Binärsuche nach dem kleinsten K durch, das diese Bedingung erfüllt.
import math
def minEatingSpeed(piles, h):
def can_finish(k):
return sum(math.ceil(p / k) for p in piles) <= h
lo, hi = 1, max(piles)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_finish(mid):
hi = mid # feasible, try lower speed
else:
lo = mid + 1 # too slow
return lo
print(minEatingSpeed([3,6,7,11], 8)) # 4
print(minEatingSpeed([30,11,23,4,20], 5)) # 30Beispiel: Minimale Tage zum Erstellen von Blumensträußen
LeetCode 1482 'Minimum Number of Days to Make m Bouquets': Sie benötigen m Blumensträuße, die jeweils aus k aufeinanderfolgenden aufgeblühten Blumen bestehen. Die Blume i blüht am Tag bloomDay[i]. Führen Sie eine Binärsuche über den Tag durch: Der Bereich ist [1, max(bloomDay)]. Die Zulässigkeitsprüfung zählt aufeinanderfolgende aufgeblühte Blumen und ermittelt, ob sich m Blumensträuße bilden lassen. Monotonieeigenschaft: Wenn Tag d funktioniert, funktioniert auch Tag d+1.
def minDays(bloomDay, m, k):
if m * k > len(bloomDay):
return -1 # impossible
def can_make(day):
bouquets = consecutive = 0
for bd in bloomDay:
if bd <= day:
consecutive += 1
if consecutive == k:
bouquets += 1
consecutive = 0
else:
consecutive = 0
return bouquets >= m
lo, hi = 1, max(bloomDay)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_make(mid):
hi = mid
else:
lo = mid + 1
return lo
print(minDays([1,10,3,10,2], 3, 1)) # 3
print(minDays([1,10,3,10,2], 3, 2)) # -1Den Suchbereich bestimmen
Die Wahl des richtigen Bereichs [lo, hi] ist entscheidend. lo sollte die kleinstmögliche Antwort sein (z. B. das kleinste Element, 1 oder 0), und hi sollte die größtmögliche Antwort sein (z. B. die Summe aller Elemente, das größte Element oder n). Wenn hi zu klein gewählt wird, werden gültige Antworten übergangen; ein zu großer Wert ist unproblematisch, da die Binärsuche trotzdem in O(log(hi - lo)) Schritten konvergiert.
# Choosing lo and hi for common problems:
# Capacity to ship: lo=max(weights), hi=sum(weights)
# Koko eating: lo=1, hi=max(piles)
# Square root: lo=1, hi=x
# Allocate books: lo=max(pages), hi=sum(pages)
def isqrt_bs(x):
if x < 2:
return x
lo, hi = 1, x
while lo < hi:
mid = lo + (hi - lo) // 2
if mid * mid <= x:
lo = mid + 1
else:
hi = mid
return lo - 1
for n in [0, 1, 4, 8, 9, 15, 16]:
print(f'isqrt({n}) = {isqrt_bs(n)}')Minimieren oder maximieren: Die Richtung ist entscheidend
Die Binärsuche über den Antwortbereich gibt es in zwei Varianten. Die Antwort minimieren: Wenn die Prüfung erfolgreich ist, versuchen Sie einen kleineren Wert (hi = mid); wenn sie fehlschlägt, versuchen Sie einen größeren Wert (lo = mid + 1). Die Antwort maximieren: Wenn die Prüfung erfolgreich ist, versuchen Sie einen größeren Wert (lo = mid + 1, wobei Sie mid als Kandidaten speichern); wenn sie fehlschlägt, versuchen Sie einen kleineren Wert (hi = mid - 1). Klären Sie immer vor dem Programmieren, in welche Richtung Sie suchen.
# Maximise: largest x such that f(x) is feasible
def max_feasible(lo, hi, is_feasible):
result = lo - 1 # sentinel: no feasible answer found
while lo <= hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
result = mid
lo = mid + 1 # try larger
else:
hi = mid - 1
return result
# Example: largest k such that k^2 <= 50
print(max_feasible(1, 50, lambda k: k * k <= 50)) # 7Minimale Seitenzahl zuweisen (klassisches Problem)
Gegeben sind n Bücher mit pages[] und k Studierenden. Weisen Sie die Bücher zusammenhängend zu, sodass der Studierende mit den meisten Seiten möglichst wenige Seiten liest. Führen Sie eine Binärsuche über die Antwort durch (das kleinstmögliche Maximum). Die Zulässigkeitsprüfung weist die Bücher greedy den Studierenden zu: Wenn das Hinzufügen eines Buches das aktuelle Maximum überschreiten würde, wird es einem neuen Studierenden zugewiesen. Wenn höchstens k Studierende benötigt werden, ist das Maximum erreichbar.
def allocate_min_pages(pages, k):
if k > len(pages):
return -1
def is_feasible(max_pages):
students, current = 1, 0
for p in pages:
if p > max_pages:
return False # single book exceeds limit
if current + p > max_pages:
students += 1
current = 0
current += p
return students <= k
lo, hi = max(pages), sum(pages)
while lo < hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
hi = mid
else:
lo = mid + 1
return lo
print(allocate_min_pages([12, 34, 67, 90], 2)) # 113
print(allocate_min_pages([10, 20, 30, 40], 2)) # 60Komplexitätsanalyse der Suche über den Antwortbereich
Die Zeitkomplexität beträgt O(n × log(range)), wobei n den Aufwand der Zulässigkeitsprüfung bezeichnet (üblicherweise ein linearer Durchlauf) und range = hi - lo die Größe des Antwortbereichs ist. Wenn sich die Seitensumme beispielsweise auf 10⁹ beläuft und die Zulässigkeitsprüfung O(n) benötigt, beträgt die Gesamtlaufzeit O(n log 10⁹) ≈ O(30n), was deutlich besser ist als eine Brute-Force-Lösung mit O(n²).
Die Speicherkomplexität der Binärsuche selbst beträgt O(1), zuzüglich des Speicherbedarfs der Zulässigkeitsprüfung.
import math
# Compare brute force vs answer-space binary search
# For sum = 10^9 and n = 10^5:
brute_ops = 10**9 # try every possible answer
bsearch_ops = 10**5 * math.log2(10**9) # n * log(range)
print(f'Brute force: {brute_ops:,.0f} operations')
print(f'Binary search: {bsearch_ops:,.0f} operations')
print(f'Speedup: {brute_ops / bsearch_ops:,.0f}x')K-kleinstes Element in einer sortierten Matrix
LeetCode 378 'Kth Smallest Element in a Sorted Matrix': Jede Zeile und jede Spalte einer n×n-Matrix ist sortiert. Führen Sie eine Binärsuche über den Antwortwert im Bereich [matrix[0][0], matrix[n-1][n-1]] durch. Die Zulässigkeitsprüfung zählt mithilfe eines Zeigers, der an der unteren linken Ecke beginnt, die Elemente <= mid und läuft in O(n). Ermitteln Sie den kleinsten Wert, für den mindestens k Elemente <= mid sind.
def kthSmallest(matrix, k):
n = len(matrix)
def count_le(mid):
count, row, col = 0, n - 1, 0
while row >= 0 and col < n:
if matrix[row][col] <= mid:
count += row + 1
col += 1
else:
row -= 1
return count
lo, hi = matrix[0][0], matrix[n-1][n-1]
while lo < hi:
mid = lo + (hi - lo) // 2
if count_le(mid) >= k:
hi = mid
else:
lo = mid + 1
return lo
matrix = [[1,5,9],[10,11,13],[12,13,15]]
print(kthSmallest(matrix, 8)) # 13Probleme mit Binärsuche über den Antwortbereich erkennen
Probleme, die sich für eine Binärsuche über den Antwortbereich eignen, weisen gemeinsame Merkmale auf: Die Frage verlangt nach einem Minimum oder Maximum, die Antwort liegt in einem begrenzten numerischen Bereich, und das Erhöhen (oder Verringern) der Kandidatenantwort macht die Zulässigkeit monoton besser oder schlechter. Typische Schlüsselwörter sind „kleinstmögliches Maximum“, „höchstens k Operationen“ und „innerhalb von d Tagen“.
Wenn Sie diese Merkmale erkennen, legen Sie sofort lo und hi fest, schreiben Sie die Zulässigkeitsfunktion und wenden Sie das Muster an. Dieser strukturierte Ansatz führt in Vorstellungsgesprächen nur selten zu Fehlern.
Kurzer Check
Testen Sie Ihr Verständnis der Konzepte von Data Structures & Algorithms — Coding Interview Prep aus dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Die Binärsuche über den Antwortbereich wird verwendet, wenn eine Zulässigkeitsfunktion über einem numerischen Bereich monoton ist, das Muster durchsucht [lo, hi] und verwendet eine can_achieve-Prüfung, um den Suchbereich zu halbieren, und die Gesam tkomplexität beträgt O(n log(range)), wobei n den Aufwand einer Zulässigkeitsprüfung bezeichnet. Als Nächstes wechseln wir zu verketteten Listen und der Node-Klasse.
Häufig gestellte Fragen
Ist die Lektion „Binäre Suche im Lösungsraum“ kostenlos?
Ja — der vollständige Text von „Binäre Suche im Lösungsraum“ 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 im Lösungsraum“?
Betrachten Sie einen kontinuierlichen Lösungsbereich als Suchraum, um Probleme wie minimum-time-to-complete-jobs und capacity-to-ship-packages zu lösen. 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 im Lösungsraum“?
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