Binary search in de antwoordruimte
Behandel een continu antwoordbereik als zoekruimte om problemen zoals minimum-time-to-complete-jobs en capacity-to-ship-packages op te lossen.
Binary search in de antwoordruimte is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 4 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Binair zoeken in de antwoordruimte
De meeste mensen kennen binair zoeken voor het vinden van een waarde in een gesorteerde array. Maar binair zoeken is nog krachtiger wanneer je het toepast op de ruimte met mogelijke antwoorden. In plaats van in een array te zoeken, zoek je in een numeriek bereik — bijvoorbeeld: 'wat is het minimale aantal dagen om alle pakketten te verzenden?' — en gebruik je een controlefunctie om te bepalen of een kandidaatantwoord haalbaar is.
Met deze techniek kun je veel optimalisatieproblemen van O(n²) of erger terugbrengen tot O(n log(max_answer)).
Het sjabloon voor de antwoordruimte
Het sjabloon heeft drie onderdelen. Definieer eerst het zoekbereik [lo, hi] dat alle geldige antwoorden omvat. Schrijf vervolgens een haalbaarheidscontrole can_achieve(mid) die True retourneert als de waarde van mid haalbaar is. Pas ten derde binair zoeken toe op [lo, hi]: als can_achieve(mid) waar is, ga je in de richting van een kleiner (of groter) antwoord; anders ga je in de andere richting.
De belangrijkste eigenschap is dat de haalbaarheidsfunctie monotoon moet zijn — zodra een antwoord haalbaar is, zijn alle waarden daarboven ook haalbaar (of zijn alle waarden eronder niet haalbaar).
# 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 resultVoorbeeld: verzendcapaciteit voor pakketten
LeetCode 1011 'Capaciteit om pakketten binnen D dagen te verzenden': gegeven een lijst met gewichten en D dagen moet je de minimale verzendcapaciteit vinden om alle pakketten in volgorde binnen D dagen te verzenden. Het antwoord ligt in [max(weights), sum(weights)]. Een capaciteit is haalbaar als een simulatie volgens een gulzige strategie alle pakketten binnen D dagen verwerkt. Binair zoeken in het capaciteitsbereik levert een tijdcomplexiteit van O(n log(sum)) op.
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)) # 6Voorbeeld: Koko eet bananen
LeetCode 875 'Koko eet bananen': Koko kan K bananen per uur eten; ze wil H stapels in precies H uur opeten en K zo klein mogelijk houden. Het zoekbereik is [1, max(piles)]. De controle: bij snelheid K is het totale aantal uren = sum(ceil(pile/K)), en dat moet <= H zijn. We zoeken binair naar de kleinste K die hieraan voldoet.
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)) # 30Voorbeeld: minimaal aantal dagen om boeketten te maken
LeetCode 1482 'Minimaal aantal dagen om m boeketten te maken': je hebt m boeketten nodig, elk met k opeenvolgende bloeiende bloemen. Bloem i bloeit op dag bloomDay[i]. Zoek binair op de dag: het bereik is [1, max(bloomDay)]. De haalbaarheidscontrole telt opeenvolgende bloeiende bloemen en controleert of er m boeketten kunnen worden gevormd. Monotone eigenschap: als dag d werkt, werkt dag d+1 ook.
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)) # -1Het zoekbereik bepalen
Het juiste bereik [lo, hi] kiezen is cruciaal. lo moet het kleinst mogelijke antwoord zijn, bijvoorbeeld het kleinste element, 1 of 0, en hi moet het grootst mogelijke antwoord zijn, bijvoorbeeld de som van alle elementen, het grootste element of n. Als je hi te klein instelt, mis je geldige antwoorden; als je hi te groot instelt, is dat geen probleem, omdat binair zoeken nog steeds in O(log(hi - lo)) stappen convergeert.
# 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)}')Maximum bepalen versus minimum bepalen: de richting is belangrijk
Binair zoeken in de antwoordruimte kent twee varianten. Het antwoord minimaliseren: als de controle slaagt, probeer je een kleinere waarde (hi = mid); als de controle mislukt, probeer je een grotere waarde (lo = mid + 1). Het antwoord maximaliseren: als de controle slaagt, probeer je een grotere waarde (lo = mid + 1 en sla je mid op als kandidaat); als de controle mislukt, probeer je een kleinere waarde (hi = mid - 1). Bepaal altijd eerst in welke richting je zoekt voordat je gaat programmeren.
# 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 pagina's toewijzen (klassiek probleem)
Gegeven n boeken met pages[] en k studenten moet je de boeken aaneengesloten toewijzen, zodat de student met de meeste pagina's er zo weinig mogelijk leest. Zoek binair naar het antwoord (het kleinst mogelijke maximum). De haalbaarheidscontrole wijst de boeken volgens een gulzige strategie toe: wanneer het toevoegen van een boek het huidige maximum zou overschrijden, geef je het aan een nieuwe student. Als er <= k studenten nodig zijn, is het maximum haalbaar.
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)) # 60Complexiteitsanalyse van zoeken in de antwoordruimte
De tijdcomplexiteit is O(n × log(range)), waarbij n de kosten van de haalbaarheidscontrole is (meestal een lineaire scan) en range = hi - lo (de omvang van de antwoordruimte). Als de som van pages bijvoorbeeld 10⁹ is en de haalbaarheidscontrole O(n) kost, is de totale tijd O(n log 10⁹) ≈ O(30n). Dat is veel beter dan O(n²) door alles uitputtend te proberen.
De ruimtecomplexiteit van het binaire zoeken zelf is O(1), plus wat de haalbaarheidscontrole gebruikt.
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-de kleinste in een gesorteerde matrix
LeetCode 378 'K-de kleinste element in een gesorteerde matrix': elke rij en kolom van een n×n-matrix is gesorteerd. Zoek binair naar de antwoordwaarde in [matrix[0][0], matrix[n-1][n-1]]. De haalbaarheidscontrole telt elementen <= mid met een aanwijzer die linksonder begint en werkt in O(n). Zoek de kleinste waarde waarvoor minstens k elementen <= mid zijn.
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)) # 13Problemen met een antwoordruimte herkennen
Problemen die geschikt zijn voor binair zoeken in de antwoordruimte hebben vaak dezelfde kenmerken: de vraag vraagt om een kleinst mogelijke of grootst mogelijke waarde, het antwoord ligt in een begrensd numeriek bereik en het verhogen (of verlagen) van het kandidaatantwoord maakt haalbaarheid monotoon beter of slechter. Klassieke trefwoorden zijn 'kleinst mogelijke maximum', 'hoogstens k bewerkingen' en 'binnen d dagen'.
Wanneer je deze kenmerken ziet, definieer je meteen lo en hi, schrijf je de haalbaarheidsfunctie en pas je het sjabloon toe. Deze gestructureerde aanpak faalt zelden tijdens technische sollicitatiegesprekken.
Korte toets
Toets je begrip van de concepten van Data Structures & Algorithms — Coding Interview Prep uit deze les.
Samenvatting van de les
In deze les heb je geleerd: binair zoeken in de antwoordruimte werkt wanneer een haalbaarheidsfunctie monotoon is over een numeriek bereik, het sjabloon zoekt in [lo, hi] en gebruikt een can_achieve-controle om de antwoordruimte te halveren en de totale complexiteit O(n log(range)) is, waarbij n de kosten van één haalbaarheidscontrole is. Hierna gaan we verder met gekoppelde lijsten en de Node-klasse.
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Binary search in de antwoordruimte” gratis?
Ja — de volledige tekst van “Binary search in de antwoordruimte” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Binary search in de antwoordruimte”?
Behandel een continu antwoordbereik als zoekruimte om problemen zoals minimum-time-to-complete-jobs en capacity-to-ship-packages op te lossen. Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 4 van 4.
Hoe lang duurt de les “Binary search in de antwoordruimte”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Klassieke binary search: links, rechts, midden
- Binary search op geroteerde en ongesorteerde arrays
- Ondergrens en bovengrens
- Binary search in de antwoordruimte