Binærsøk i svarområdet
Behandle et kontinuerlig svarintervall som et søkeområde for å løse problemer som minimum-time-to-complete-jobs og capacity-to-ship-packages.
Binærsøk i svarområdet er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 4 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Binærsøk i svarområdet
De fleste kjenner binærsøk som en metode for å finne en verdi i et sortert array. Men binærsøk er enda kraftigere når det brukes på området av mulige svar. I stedet for å søke i et array søker De i et numerisk intervall — for eksempel «hva er minimumsantallet dager som trengs for å sende alle pakkene?» — og bruker en kontrollfunksjon til å avgjøre om et mulig svar lar seg gjennomføre.
Denne teknikken gjør mange optimaliseringsproblemer med O(n²) eller verre om til O(n log(max_answer)).
Malen for svarområdet
Malen består av tre komponenter. Først definerer De søkeområdet [lo, hi] som omslutter alle gyldige svar. Deretter skriver De en gjennomførbarhetskontroll can_achieve(mid) som returnerer True hvis mid-verdien kan oppnås. Til slutt utfører De binærsøk over [lo, hi]: Hvis can_achieve(mid) er sann, beveger De Dem mot et mindre (eller større) svar; ellers beveger De Dem i motsatt retning.
Den viktige egenskapen er at gjennomførbarhetsfunksjonen må være monoton — når et svar først er gjennomførbart, er alle verdier over det også gjennomførbare (eller alle verdier under det ugjennomførbare).
# 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 resultEksempel: Kapasitet til å sende pakker
LeetCode 1011 «Kapasitet til å sende pakker innen D dager»: Gitt en liste med vekter og D dager skal du finne den minste fraktkapasiteten som kan sende alle pakkene i riktig rekkefølge innen D dager. Svaret ligger i [max(weights), sum(weights)]. En kapasitet er gjennomførbar hvis en grådig simulering får plass til alle pakkene innen D dager. Binærsøk over kapasitetsintervallet gir tidskompleksiteten 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)) # 6Eksempel: Koko spiser bananer
LeetCode 875 «Koko spiser bananer»: Koko kan spise K bananer i timen. Hun vil spise opp H hauger på nøyaktig H timer og minimere K. Søkeintervallet er [1, max(piles)]. Sjekken er følgende: Ved hastighet K er totalt antall timer = sum(ceil(pile/K)), og dette må være <= H. Vi bruker binærsøk for å finne den minste K som oppfyller dette.
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)) # 30Eksempel: Minste antall dager for å lage buketter
LeetCode 1482 «Minste antall dager for å lage m buketter»: Du trenger m buketter, hver med k sammenhengende utsprungne blomster. Blomst i springer ut på dag bloomDay[i]. Bruk binærsøk på dagen: intervallet er [1, max(bloomDay)]. Gjennomførbarhetssjekken teller sammenhengende utsprungne blomster og ser om det kan dannes m buketter. Monoton egenskap: Hvis dag d fungerer, fungerer også 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)) # -1Finne søkeintervallet
Det er avgjørende å velge riktig [lo, hi]-intervall. lo bør være det minste mulige svaret (for eksempel det minste elementet, 1 eller 0), og hi bør være det største mulige svaret (for eksempel summen av alle elementene, det største elementet eller n). Hvis hi settes for lavt, utelates gyldige svar. Det er derimot greit å sette det for høyt, fordi binærsøket likevel konvergerer på O(log(hi - lo)) trinn.
# 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)}')Maksimere eller minimere: Retningen er viktig
Binærsøk over svarområdet har to varianter. Minimer svaret: Når sjekken lykkes, prøver du mindre verdier (hi = mid). Når den mislykkes, prøver du større verdier (lo = mid + 1). Maksimer svaret: Når sjekken lykkes, prøver du større verdier (lo = mid + 1 og lagrer mid som kandidat). Når den mislykkes, prøver du mindre verdier (hi = mid - 1). Avklar alltid hvilken retning du søker i, før du begynner å skrive kode.
# 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)) # 7Minimumssider ved bokfordeling (klassisk problem)
Gitt n bøker med pages[] og k studenter skal du fordele bøkene sammenhengende slik at studenten som får flest sider, leser så få sider som mulig. Bruk binærsøk på svaret (det minste mulige maksimumet). Gjennomførbarhetssjekken fordeler bøkene grådig til studentene: Når en bok vil føre til at det nåværende maksimumet overskrides, gis den til en ny student. Hvis antallet studenter som trengs er <= k, kan maksimumet oppnås.
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)) # 60Kompleksitetsanalyse for søk i svarområdet
Tidskompleksiteten er O(n × log(range)), der n er kostnaden for gjennomførbarhetssjekken (vanligvis en lineær gjennomgang), og range = hi - lo (størrelsen på svarområdet). Hvis sidetallet for eksempel summerer seg til 10⁹ og gjennomførbarhetssjekken er O(n), blir den totale tiden O(n log 10⁹) ≈ O(30n), som er langt bedre enn O(n²) med brut force.
Plasskompleksiteten er O(1) for selve binærsøket, i tillegg til det gjennomførbarhetssjekken bruker.
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 minste elementet i en sortert matrise
LeetCode 378 «Det k-te minste elementet i en sortert matrise»: Hver rad og kolonne i en n×n-matrise er sortert. Bruk binærsøk på svarets verdi i [matrix[0][0], matrix[n-1][n-1]]. Gjennomførbarhetssjekken teller elementer <= mid ved hjelp av en peker som starter nederst til venstre, og kjører på O(n). Finn den minste verdien der minst k elementer er <= 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)) # 13Gjenkjenne problemer for søk i svarområdet
Problemer som egner seg for binærsøk over svarområdet, har noen felles kjennetegn: Oppgaven ber om en minste eller største verdi, svaret ligger i et avgrenset numerisk intervall, og når kandidatverdien økes (eller reduseres), blir gjennomførbarheten monotont bedre eller verre. Klassiske nøkkeluttrykk er «minste mulige maksimum», «høyst k operasjoner» og «innen d dager».
Når du oppdager disse kjennetegnene, bør du straks definere lo og hi, skrive gjennomførbarhetsfunksjonen og bruke malen. Denne strukturerte tilnærmingen slår sjelden feil i intervjuer.
Kort test
Test forståelsen din av konseptene i Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen har du lært at binærsøk over svarområdet brukes når en gjennomførbarhetsfunksjon er monoton over et numerisk intervall, at malen søker i [lo, hi] og bruker en can_achieve-sjekk for å halvere søkeområdet, og at den totale kompleksiteten er O(n log(range)), der n er kostnaden for én gjennomførbarhetssjekk. Neste tema er lenkede lister og Node-klassen.
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Binærsøk i svarområdet» gratis?
Ja – hele teksten i «Binærsøk i svarområdet» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Binærsøk i svarområdet»?
Behandle et kontinuerlig svarintervall som et søkeområde for å løse problemer som minimum-time-to-complete-jobs og capacity-to-ship-packages. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 4 av 4.
Hvor lang tid tar leksjonen «Binærsøk i svarområdet»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Klassisk binærsøk: venstre, høyre, midt
- Binærsøk i roterte og usorterte arrayer
- Nedre og øvre grense
- Binærsøk i svarområdet