Klassisk binærsøk: venstre, høyre, midt
Implementer binærsøk iterativt og rekursivt, få kontroll på detaljene med én avvik for lo/hi-grenser, og verifiser korrektheten med kanttilfeller.
Klassisk binærsøk: venstre, høyre, midt er en gratis leksjon i DSA Interview Prep på CoddyKit. Dette er leksjon 1 av 4. Du kan lese valgfritt 3 leksjoner fra denne læringsstien gratis i sin helhet – deretter låser CoddyKit PRO opp alle leksjoner, samt praktisk øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i DSA Interview Prep, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.
Hvorfor binærsøk er viktig
Binærsøk reduserer et lineært søk på O(n) til O(log n) ved å halvere søkeområdet for hvert trinn. I en array med én million elementer krever et lineært søk opptil 1 000 000 sammenligninger, mens binærsøk krever høyst 20. Denne effektiviteten gjør binærsøk til en av algoritmene som oftest testes i kodeintervjuer.
Kjerneinnsikten er at en sortert array lar deg avgjøre, etter én sammenligning, hvilken halvdel av de gjenværende dataene som kan forkastes fullstendig.
Rammeverket venstre–midt–høyre
Binærsøk bruker tre indekspekere: lo (venstre grense), hi (høyre grense) og mid (midtpunktet). I hver iterasjon beregner du mid = (lo + hi) // 2 og sammenligner målet med arr[mid]. Hvis målet er mindre, flytter du hi = mid - 1; hvis det er større, flytter du lo = mid + 1; hvis det er likt, har du funnet det.
Løkken fortsetter så lenge lo <= hi. Når løkken avsluttes uten at målet er funnet, returnerer du -1.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9, 11], 7)) # 3
print(binary_search([1, 3, 5, 7, 9, 11], 6)) # -1Unngå heltallsoverflyt i midtpunktet
Uttrykket mid = (lo + hi) // 2 kan føre til heltallsoverflyt i språk med heltall med fast bredde (Java, C++). Python-heltall har vilkårlig presisjon, så overflyt oppstår aldri, men intervjuere forventer likevel at du kjenner det trygge alternativet: mid = lo + (hi - lo) // 2.
Denne formen beregner det samme midtpunktet, men legger bare halve avstanden til lo i stedet for å summere begge pekerne først. Hvis du nevner dette i et intervju, viser du at du er oppmerksom på hensyn på lavt nivå.
# Safe mid calculation (important in Java/C++, good habit in Python too)
lo, hi = 0, 1_000_000_000
mid_unsafe = (lo + hi) // 2 # fine in Python
mid_safe = lo + (hi - lo) // 2 # same result, no overflow risk
print(mid_unsafe == mid_safe) # TrueInklusive og eksklusive grenser
Noe av det vanskeligste ved binærsøk er å velge om hi peker på den siste gyldige indeksen (inklusive, hi = len(arr) - 1) eller én posisjon etter slutten (eksklusiv, hi = len(arr)). Ulike konvensjoner krever ulike løkkebetingelser og oppdateringer av grensene.
Med inklusive grenser bruker du while lo <= hi og oppdaterer hi = mid - 1. Med eksklusive grenser bruker du while lo < hi og oppdaterer hi = mid. Å blande konvensjoner er den vanligste årsaken til feil i implementasjoner av binærsøk.
# Exclusive hi variant — useful for bisect-style lower-bound
def search_exclusive(arr, target):
lo, hi = 0, len(arr) # hi is one past last
while lo < hi: # strictly less than
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid # NOT mid - 1
return lo if lo < len(arr) and arr[lo] == target else -1
print(search_exclusive([2, 4, 6, 8, 10], 6)) # 2Rekursivt binærsøk
Binærsøk kan skrives rekursivt ved å sende oppdaterte grenser for lo og hi gjennom kallstakken. Hvert rekursive kall halverer søkeområdet, så dybden er O(log n). Basistilfellet oppstår når lo > hi (ikke funnet) eller arr[mid] == target (funnet).
Den iterative versjonen foretrekkes i produksjonskode fordi den unngår overhead fra stakkrammer, men den rekursive versjonen kommuniserer del-og-hersk-strukturen tydeligere på en tavle.
def binary_search_rec(arr, target, lo, hi):
if lo > hi:
return -1
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_rec(arr, target, mid + 1, hi)
else:
return binary_search_rec(arr, target, lo, mid - 1)
arr = [1, 3, 5, 7, 9, 11]
print(binary_search_rec(arr, 9, 0, len(arr) - 1)) # 4Kanttilfeller: tom array, ett element
Et robust binærsøk må håndtere kanttilfeller uten å krasje. De tre vanligste er: en tom array (løkken kjøres aldri, og -1 returneres korrekt), en array med ett element (mid er lik lo og hi, så én sammenligning er nok) og mål utenfor området (lo blir til slutt større enn hi, og -1 returneres).
Kontroller alltid implementasjonen med disse inndataene før du går videre til oppfølgingsspørsmål i et intervju.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print(binary_search([], 5)) # -1 (empty)
print(binary_search([7], 7)) # 0 (single, found)
print(binary_search([7], 3)) # -1 (single, not found)
print(binary_search([1,3,5], 0)) # -1 (below range)
print(binary_search([1,3,5], 9)) # -1 (above range)Tids- og plasskompleksitet
Binærsøk har tidskompleksiteten O(log n) fordi hver sammenligning halverer søkeområdet. Etter k sammenligninger er det gjenværende området n/2^k; søket avsluttes når dette blir 1, så k = log₂ n.
Plasskompleksiteten er O(1) for den iterative versjonen (bare tre heltallsvariabler) og O(log n) for den rekursive versjonen på grunn av kallstakkens dybde. I et intervju bør du alltid oppgi begge og foretrekke den iterative formen når plassen er begrenset.
import math
for n in [10, 100, 1000, 1_000_000, 1_000_000_000]:
steps = math.ceil(math.log2(n + 1))
print(f'n={n:>12,} max comparisons={steps}')Søk etter nøyaktig treff eller grense
Klassisk binærsøk returnerer en vilkårlig indeks der målet finnes. Men mange intervjuproblemer ber om den første eller siste forekomsten av et mål. Da må du fortsette søket selv etter at du har funnet et treff – i stedet for å returnere umiddelbart snevrer du inn grensen og fortsetter.
Når du søker etter den første forekomsten, lagrer du mid som kandidat etter at du har funnet arr[mid] == target, og setter hi = mid - 1. For den siste forekomsten setter du lo = mid + 1.
def first_occurrence(arr, target):
lo, hi, result = 0, len(arr) - 1, -1
while lo <= hi:
mid = lo + (hi - lo) // 2
if arr[mid] == target:
result = mid
hi = mid - 1 # keep searching left
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return result
print(first_occurrence([1, 2, 2, 2, 3], 2)) # 1Bruk av Pythons bisect-modul
Pythons standardbibliotek tilbyr bisect.bisect_left(arr, x) og bisect.bisect_right(arr, x) for produksjonsklar implementering av binærsøk. bisect_left returnerer indeksen lengst til venstre der x kan settes inn slik at arrayet forblir sortert, og finner dermed i praksis den første posisjonen der arr[i] >= x.
Intervjuere kan tillate at du bruker bisect; avklar alltid dette først. Det er fortsatt viktig å vite hvordan modulen fungerer under panseret (den bruker binærsøk med O(log n)).
import bisect
arr = [1, 2, 2, 2, 3, 5]
print(bisect.bisect_left(arr, 2)) # 1 (first 2)
print(bisect.bisect_right(arr, 2)) # 4 (after last 2)
# Check if target exists
target = 3
idx = bisect.bisect_left(arr, target)
print(idx < len(arr) and arr[idx] == target) # TrueVanlige fallgruver ved binærsøk
Tre feil fører til de fleste feilene i binærsøk under intervjuer. For det første, feil løkkebetingelse: Hvis du bruker < i stedet for <= med inklusive grenser, hoppes det siste gjenværende elementet over. For det andre, feil oppdatering av grensene: Hvis du glemmer +1 eller -1, oppstår det en uendelig løkke når lo == hi. For det tredje, å arbeide med en usortert array: Binærsøk er bare korrekt for sorterte data.
Si alltid høyt før du skriver et binærsøk: «Arrayet er sortert, grensene mine er inklusive, og løkken kjører så lenge lo <= hi.»
# BUG: infinite loop when lo == hi because hi = mid never moves past lo
def buggy(arr, target):
lo, hi = 0, len(arr) - 1
while lo < hi: # should be lo <= hi for exact-match
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid # stops, but never returns mid when found
return lo if arr[lo] == target else -1
print(buggy([1, 3, 5, 7], 7)) # 3 (works here by luck)
print(buggy([1, 3, 5, 7], 1)) # 0 (correct)
print(buggy([1, 3, 5, 7], 4)) # -1 (correct)Intervjutips for binærsøk
Når du ser et problem med en sortert array, en monotont økende funksjon eller et søkeområde som kan halveres, bør du umiddelbart vurdere binærsøk. Fortell tankegangen din i et intervju: «Siden arrayet er sortert, kan jeg forkaste halvparten av elementene for hver sammenligning, noe som gir O(log n).»
Kontroller alltid løsningen med minst tre inndata: en verdi i begynnelsen, en verdi på slutten og en verdi som mangler. Hvis du oppgir kompleksiteten på eget initiativ – «tid O(log n), plass O(1)» – før du blir spurt, viser det at du har et sterkt grunnlag.
Hurtigsjekk
Test forståelsen din av konseptene fra Data Structures & Algorithms — Coding Interview Prep i denne leksjonen.
Leksjonsoppsummering
I denne leksjonen lærte du: binærsøk halverer søkeområdet for hvert trinn og bruker O(log n) tid, konvensjonen med inklusive grenser bruker lo <= hi, med oppdateringene lo = mid+1 og hi = mid-1, og for å finne første eller siste forekomst fortsetter du søket etter et treff i stedet for å returnere umiddelbart. Neste gang skal vi se på hvordan binærsøk kan utvides til roterte og usorterte arrayer.
Lær deg Python 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
- 30
- Leksjoner
- 120
Ofte stilte spørsmål
Er leksjonen «Klassisk binærsøk: venstre, høyre, midt» gratis?
Ja – du kan lese valgfritt 3 av leksjonene i læringsstien DSA Interview Prep, inkludert «Klassisk binærsøk: venstre, høyre, midt», gratis i sin helhet her på nettet. Deretter låser CoddyKit PRO opp alle leksjoner, samt interaktiv øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.
Hva lærer jeg i «Klassisk binærsøk: venstre, høyre, midt»?
Implementer binærsøk iterativt og rekursivt, få kontroll på detaljene med én avvik for lo/hi-grenser, og verifiser korrektheten med kanttilfeller. Du øver på DSA Interview Prep 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 DSA Interview Prep?
Ingen tidligere erfaring er nødvendig. DSA Interview Prep 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 1 av 4.
Hvor lang tid tar leksjonen «Klassisk binærsøk: venstre, høyre, midt»?
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 DSA Interview Prep-leksjonen?
Ja. Alle DSA Interview Prep-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