Binary search halveert de zoekruimte bij elke stap. In een gesorteerde array van n elementen vind je een doelwaarde in O(log n) tijd.
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
Eenvoudig - maar de echte kracht van binary search reikt veel verder dan gesorteerde arrays.
Binary search werkt wanneer er een monotone conditie over een bereik bestaat. De "array" hoeft niet eens te bestaan - je hebt alleen een bereik [lo, hi] nodig en een functie die van False naar True (of andersom) omslaagt bij een grens.
Search space: [lo .................. hi]
Condition: F F F F T T T T
^-- answer
In plaats van in een array te zoeken, doorzoek je de antwoordruimte. Vraag: "Kan ik resultaat X bereiken?" Zo ja, probeer kleiner; zo nee, probeer groter.
Koko heeft n stapels bananen en h uur. Vind de minimale eetsnelheid zodat ze op tijd klaar is.
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
De antwoordruimte is [1, max(piles)] en de conditie is monotoon - hogere snelheid betekent altijd minder uren.
Sign in to join the discussion
Een gesorteerde array geroteerd bij een draaipunt: [4, 5, 6, 7, 0, 1, 2]. Eén helft is altijd gesorteerd. Vergelijk mid met lo om te bepalen welke helft, en kijk dan of het doel in de gesorteerde helft valt.
[4, 5, 6, 7, 0, 1, 2]
L M R
Left half [4..7] is sorted.
Target 1 not in [4..7] → search right.
In een geroteerde gesorteerde array [3,4,5,1,2], welke helft is gesorteerd als mid=2 (waarde 5)?
Om het eerste voorkomen te vinden: als je het doel raakt, stop dan niet - zet hi = mid en blijf links zoeken. Voor het laatste: zet lo = mid + 1 en zoek rechts.
Dit paar zoekopdrachten geeft je ook het aantal voorkomens: last - first + 1.
Een element dat groter is dan beide buren. Zelfs in een ongesorteerde array werkt binary search: als nums[mid] < nums[mid + 1], ligt de piek rechts; anders links. O(log n).
Als rijen gesorteerd zijn en het eerste element van elke rij groter is dan het laatste van de vorige, behandel de matrix dan als één gesorteerde array van m × n elementen. Map index k naar rij k // n, kolom k % n.
Vind het grootste gehele getal x waarvoor x * x ≤ n. Zoekruimte: [0, n]. Klassieke binary search op het antwoord.
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
Problemen als "split array largest sum" of "capacity to ship packages within D days" vragen je om het slechtste geval te minimaliseren. Het antwoord is monotoon: als capaciteit C werkt, werkt C+1 ook. Binary search op C.
Wat is de zoekruimte voor binary search bij 'Capacity to Ship Packages in D Days'?
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
Pas hi = mid vs lo = mid aan naargelang je de eerste True of laatste True zoekt.
Wat is de tijdscomplexiteit van binary search op een antwoordruimte van grootte S met een O(n) haalbaarheidscheck?