Binärsökning i svarsrummet
Behandla ett kontinuerligt svarsintervall som sökutrymme för att lösa problem som minimum-time-to-complete-jobs och capacity-to-ship-packages.
Binärsökning i svarsrummet är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 4 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Binärsökning över svarsrummet
De flesta känner till binärsökning för att hitta ett värde i en sorterad array. Men binärsökning blir ännu kraftfullare när den tillämpas på mängden av möjliga svar. I stället för att söka i en array söker man i ett numeriskt intervall — till exempel ”vilket är det minsta antalet dagar som krävs för att skicka alla paket?” — och använder en kontrollfunktion för att avgöra om ett kandidatsvar är genomförbart.
Med den här tekniken kan många optimeringsproblem omvandlas från O(n²) eller sämre till O(n log(max_answer)).
Mallen för svarsrumsbinärsökning
Mallen har tre delar. Först definierar man sökintervallet [lo, hi] som omsluter alla giltiga svar. Sedan skriver man en genomförbarhetskontroll can_achieve(mid) som returnerar True om mid-värdet går att uppnå. Till sist utför man binärsökning över [lo, hi]: om can_achieve(mid) är sant flyttar man sig mot ett mindre (eller större) svar; annars går man åt andra hållet.
Den viktiga egenskapen är att genomförbarhetsfunktionen måste vara monoton — när ett svar väl är genomförbart är alla större värden också genomförbara (eller så är alla mindre värden ogenomförbara).
# 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 resultExempel: Kapacitet för att frakta paket
LeetCode 1011 'Kapacitet för att frakta paket inom D dagar': ni får en lista med vikter och D dagar och ska hitta den minsta fraktkapacitet som krävs för att frakta alla paket i ordning inom D dagar. Svaret ligger i [max(weights), sum(weights)]. En kapacitet är genomförbar om en girig simulering får plats med alla paket inom D dagar. Binärsökning över kapacitetsintervallet ger tidskomplexiteten 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)) # 6Exempel: Koko äter bananer
LeetCode 875 'Koko äter bananer': Koko kan äta K bananer i timmen. Hon vill äta upp H högar på exakt H timmar och minimera K. Sökintervallet är [1, max(piles)]. Kontrollen: vid hastigheten K är det totala antalet timmar = sum(ceil(pile/K)), vilket måste vara <= H. Vi gör en binärsökning efter det minsta K som uppfyller detta.
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)) # 30Exempel: Minsta antal dagar för att göra buketter
LeetCode 1482 'Minsta antal dagar för att göra m buketter': ni behöver m buketter, där varje bukett består av k sammanhängande blommor som har slagit ut. Blomma i slår ut på dagen bloomDay[i]. Gör en binärsökning över dagen: intervallet är [1, max(bloomDay)]. Genomförbarhetskontrollen räknar sammanhängande blommor som har slagit ut och avgör om m buketter kan skapas. Monotonicitet: om dag d fungerar, fungerar även dag 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)) # -1Identifiera sökintervallet
Att välja rätt [lo, hi]-intervall är avgörande. lo bör vara det minsta möjliga svaret (till exempel det minsta elementet, 1 eller 0), och hi bör vara det största möjliga svaret (till exempel summan av alla element, det största elementet eller n). Om hi sätts för lågt missas giltiga svar. Att sätta det för högt är däremot inget problem, eftersom binärsökningen ändå konvergerar på O(log(hi - lo)) steg.
# 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)}')Maximera eller minimera: riktningen spelar roll
Binärsökning i svarsrummet finns i två varianter. Minimera svaret: när kontrollen lyckas provar ni mindre värden (hi = mid), och när den misslyckas provar ni större värden (lo = mid + 1). Maximera svaret: när kontrollen lyckas provar ni större värden (lo = mid + 1 och sparar mid som kandidat), och när den misslyckas provar ni mindre värden (hi = mid - 1). Klargör alltid åt vilket håll ni söker innan ni börjar koda.
# 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)) # 7Tilldela minsta antal sidor (klassisk uppgift)
Med n böcker med pages[] och k studenter ska ni fördela böckerna i sammanhängande block, så att studenten som läser flest sidor läser så få som möjligt. Gör en binärsökning över svaret (det minsta möjliga maxvärdet). Genomförbarhetskontrollen tilldelar böcker girigt: när en bok skulle göra att det aktuella maxvärdet överskrids, tilldelas den en ny student. Om antalet studenter som behövs är <= k är maxvärdet möjligt att uppnå.
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)) # 60Komplexitetsanalys av sökning i svarsrummet
Tidskomplexiteten är O(n × log(range)), där n är kostnaden för genomförbarhetskontrollen (vanligen en linjär genomgång) och range = hi - lo (svarsrummets storlek). Om sidorna till exempel summerar till 10⁹ och genomförbarhetskontrollen är O(n), blir den totala tidskomplexiteten O(n log 10⁹) ≈ O(30n), vilket är betydligt bättre än O(n²) med brute force.
Rymdkomplexiteten är O(1) för själva binärsökningen, plus det minne som genomförbarhetskontrollen använder.
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')Det k:te minsta elementet i en sorterad matris
LeetCode 378 'Det k:te minsta elementet i en sorterad matris': varje rad och kolumn i en n×n-matris är sorterad. Gör en binärsökning över svarsvärdet i [matrix[0][0], matrix[n-1][n-1]]. Genomförbarhetskontrollen räknar element som är <= mid med hjälp av en pekare som börjar i det nedre vänstra hörnet och körs på O(n). Hitta det minsta värdet där minst k element är <= mid.
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)) # 13Känna igen problem i svarsrummet
Problem som lämpar sig för binärsökning i svarsrummet har gemensamma kännetecken: frågan efterfrågar ett minsta eller största värde, svaret ligger i ett begränsat numeriskt intervall, och om ni ökar (eller minskar) kandidatvärdet blir genomförbarheten monotont bättre eller sämre. Klassiska nyckelfraser är 'minsta möjliga maxvärde', 'högst k operationer' och 'inom d dagar'.
När ni upptäcker dessa kännetecken bör ni omedelbart definiera lo och hi, skriva genomförbarhetsfunktionen och använda mallen. Det här strukturerade tillvägagångssättet misslyckas sällan på intervjuer.
Snabbtest
Testa er förståelse av koncepten i Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Sammanfattning
I den här lektionen lärde ni er: binärsökning i svarsrummet används när en genomförbarhetsfunktion är monoton över ett numeriskt intervall, mallen söker i [lo, hi] och använder en can_achieve-kontroll för att halvera sökutrymmet, och den totala komplexiteten är O(n log(range)), där n är kostnaden för en genomförbarhetskontroll. Härnäst går vi över till länkade listor och klassen Node.
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Binärsökning i svarsrummet” gratis?
Ja – hela texten till ”Binärsökning i svarsrummet” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Binärsökning i svarsrummet”?
Behandla ett kontinuerligt svarsintervall som sökutrymme för att lösa problem som minimum-time-to-complete-jobs och capacity-to-ship-packages. Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.
Hur lång tid tar lektionen ”Binärsökning i svarsrummet”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Klassisk binärsökning: vänster, höger, mitten
- Binärsökning i roterade och osorterade arrayer
- Nedre och övre gräns
- Binärsökning i svarsrummet