Die binäre Suche halbiert den Suchraum bei jedem Schritt. In einem sortierten Array mit n Elementen wird in O(log n) Zeit ein Ziel gefunden.
def binary_search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
Ganz einfach – aber die wahre Stärke der binären Suche geht weit über sortierte Arrays hinaus.
Die binäre Suche funktioniert immer dann, wenn in einem Bereich eine monotone Bedingung vorliegt. Das „Array“ muss nicht einmal existieren – Sie benötigen lediglich einen Bereich [lo, hi] und eine Funktion, die an einer Grenze von False auf True (oder umgekehrt) wechselt.
Search space: [lo .................. hi]
Condition: F F F F T T T T
^-- answer
Anstatt ein Array zu durchsuchen, durchsuchen Sie den Antwortbereich. Fragen Sie: „Kann ich Ergebnis X erreichen?“ Wenn ja, versuchen Sie es mit einer kleineren Größe. Wenn nicht, versuchen Sie es größer.
Koko hat n Haufen Bananen und h Stunden. Finden Sie die minimale Fressgeschwindigkeit, damit sie rechtzeitig fertig ist.
def min_speed(piles, h):
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
hours = sum((p + mid - 1) // mid for p in piles)
if hours <= h:
hi = mid # speed works, try slower
else:
lo = mid + 1 # too slow, go faster
return lo
Der Antwortraum ist [1, max(piles)] und die Bedingung ist monoton – höhere Geschwindigkeit bedeutet immer weniger Stunden.
Anmelden an der Diskussion teilnehmen
Ein sortiertes Array, das an einem Drehpunkt gedreht wurde: [4, 5, 6, 7, 0, 1, 2]. Eine Hälfte ist immer sortiert. Vergleichen Sie mid mit lo, um zu entscheiden, welche Hälfte und prüfen Sie dann, ob das Ziel in die sortierte Hälfte fällt.
[4, 5, 6, 7, 0, 1, 2]
L M R
Left half [4..7] is sorted.
Target 1 not in [4..7] → search right.
Welche Hälfte wird in einem gedrehten sortierten Array [3,4,5,1,2] sortiert, wenn mid=2 (Wert 5)?
Um das erste Vorkommen zu finden, halten Sie nicht an, wenn Sie das Ziel erreichen, sondern stellen Sie hi = mid ein und suchen Sie weiter nach links. Für den letzten stellen Sie lo = mid + 1 ein und suchen nach rechts.
Dieses Suchpaar liefert Ihnen auch die Anzahl eines Ziels: last - first + 1.
Ein Element, das größer als beide Nachbarn ist. Selbst in einem unsortierten Array funktioniert die binäre Suche: Bei nums[mid] < nums[mid + 1] liegt der Peak rechts; sonst ist es links. O(log n).
Wenn Zeilen sortiert sind und das erste Element jeder Zeile größer als das letzte der vorherigen ist, behandeln Sie die Matrix als ein einzelnes sortiertes Array von m × n Elementen. Ordnen Sie den Index k der Zeile k // n und der Spalte k % n zu.
Finden Sie die größte ganze Zahl x mit x * x ≤ n. Suchraum: [0, n]. Klassische binäre Suche nach Antwort.
def sqrt(n):
lo, hi = 0, n
while lo <= hi:
mid = (lo + hi) // 2
if mid * mid <= n:
lo = mid + 1
else:
hi = mid - 1
return hi
Bei Problemen wie „Split Array größte Summe“ oder „Kapazität zum Versenden von Paketen innerhalb von D Tagen“ müssen Sie den schlimmsten Fall minimieren. Die Antwort ist monoton: Wenn die Kapazität C funktioniert, funktioniert auch C+1. Binäre Suche auf C.
Wie groß ist der Suchraum für die binäre Suche bei „Kapazität zum Versenden von Paketen in D Tagen”?
lo, hi = min_possible, max_possible
while lo < hi:
mid = (lo + hi) // 2
if condition(mid):
hi = mid # mid works, try smaller
else:
lo = mid + 1 # mid fails, need larger
return lo
Passen Sie hi = mid gegenüber lo = mid an, je nachdem, ob Sie das erste Wahre oder das letzte Wahre suchen.
Wie groß ist die zeitliche Komplexität der binären Suche auf einem Antwortraum der Größe S mit einer O(n)-Machbarkeitsprüfung?