Klassisk binärsökning: vänster, höger, mitten
Implementera binärsökning iterativt och rekursivt, få koll på off-by-one-detaljer för lo/hi-gränser och verifiera korrektheten med kantfallsindata.
Klassisk binärsökning: vänster, höger, mitten är en gratis lektion i DSA Interview Prep på CoddyKit. Detta är lektion 1 av 4. Du kan läsa vilka 3 lektioner som helst i den här lärvägen kostnadsfritt i sin helhet – därefter låser CoddyKit PRO upp alla lektioner, plus praktisk övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Den ingår i lärvägen för DSA Interview Prep, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Varför binärsökning är viktig
Binärsökning minskar en linjär genomsökning på O(n) till O(log n) genom att halvera sökutrymmet i varje steg. I en array med en miljon element kräver en linjär genomsökning upp till 1 000 000 jämförelser, medan binärsökning kräver högst 20. Denna effektivitet gör den till en av de algoritmer som testas oftast i kodningsintervjuer.
Den centrala insikten är att en sorterad array låter dig avgöra, efter en enda jämförelse, vilken hälft av den återstående datan som helt kan förkastas.
Ramverket vänster, mitten, höger
Binärsökning använder tre indexpekare: lo (vänstergräns), hi (högergräns) och mid (mittpunkt). Vid varje iteration beräknar du mid = (lo + hi) // 2 och jämför målet med arr[mid]. Om målet är mindre flyttar du hi = mid - 1; om det är större flyttar du lo = mid + 1; om det är lika har du hittat det.
Loopen fortsätter så länge lo <= hi. När loopen avslutas utan att målet hittas returnerar 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)) # -1Undvika heltalsöverflöde i mid
Uttrycket mid = (lo + hi) // 2 kan orsaka heltalsöverflöde i språk med heltal med fast bredd (Java, C++). Pythons heltal har godtycklig precision, så överflöde inträffar aldrig, men intervjuare förväntar sig ändå att du känner till det säkra alternativet: mid = lo + (hi - lo) // 2.
Den här formen beräknar samma mittpunkt men adderar bara halva avståndet till lo i stället för att först summera båda pekarna. Att nämna detta i en intervju visar att du är medveten om problem på låg 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) # TrueInkluderande kontra exkluderande gränser
En av de knepigaste delarna av binärsökning är att välja om hi pekar på det sista giltiga indexet (inkluderande, hi = len(arr) - 1) eller på positionen efter slutet (exkluderande, hi = len(arr)). Olika konventioner kräver olika loopvillkor och gränsuppdateringar.
Med inkluderande gränser använder du while lo <= hi och uppdaterar hi = mid - 1. Med exkluderande gränser använder du while lo < hi och uppdaterar hi = mid. Att blanda ihop konventionerna är den vanligaste orsaken till buggar i implementationer av binärsökning.
# 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)) # 2Rekursiv binärsökning
Binärsökning kan skrivas rekursivt genom att skicka uppdaterade gränser för lo och hi genom anropsstacken. Varje rekursivt anrop halverar sökutrymmet, så djupet är O(log n). Basfallet är när lo > hi (hittades inte) eller arr[mid] == target (hittades).
Den iterativa versionen föredras i produktionskod eftersom den undviker overhead för stackramar, men den rekursiva versionen förmedlar divide-and-conquer-strukturen tydligare på en whiteboard.
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)) # 4Specialfall: tom array, ett element
En robust binärsökning måste hantera specialfall utan att krascha. De tre vanligaste är: en tom array (loopen körs aldrig och -1 returneras korrekt), en array med ett element (mid är lika med lo och hi, så en jämförelse räcker) samt målvärden utanför intervallet (lo överskrider så småningom hi och -1 returneras).
Kontrollera alltid implementationen mot dessa indata innan du går vidare till följdfrågor i en 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- och minneskomplexitet
Binärsökning har tidskomplexiteten O(log n) eftersom varje jämförelse halverar sökutrymmet. Efter k jämförelser återstår n/2^k element; sökningen avslutas när detta når 1, så k = log₂ n.
Minneskomplexiteten är O(1) för den iterativa versionen (endast tre heltalsvariabler) och O(log n) för den rekursiva versionen på grund av anropsstackens djup. Ange alltid båda i en intervju och föredra den iterativa formen när minnesutrymmet är begränsat.
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öka efter exakt träff kontra gräns
Klassisk binärsökning returnerar vilket index som helst där målet finns. Men många intervjuproblem frågar efter den första eller sista förekomsten av ett mål. Då måste du fortsätta söka även efter att du hittat en träff – i stället för att returnera direkt begränsar du gränsen och fortsätter.
När du söker efter den första förekomsten ska du, efter att ha hittat arr[mid] == target, spara mid som kandidat och ange hi = mid - 1. För den sista förekomsten anger 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)) # 1Använda Pythons bisect-modul
Pythons standardbibliotek tillhandahåller bisect.bisect_left(arr, x) och bisect.bisect_right(arr, x) för binärsökning redo för produktionsbruk. bisect_left returnerar det index längst till vänster där x kan infogas för att behålla arrayen sorterad, vilket i praktiken hittar den första positionen där arr[i] >= x.
Intervjuare kan tillåta dig att använda bisect; be alltid om bekräftelse först. Det är fortfarande viktigt att veta hur den fungerar bakom kulisserna (det är binärsökning på 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) # TrueVanliga fallgropar vid binärsökning
Tre misstag orsakar de flesta buggar i binärsökning under intervjuer. För det första, felaktigt loopvillkor: att använda < i stället för <= med inkluderande gränser gör att det sista återstående elementet hoppas över. För det andra, felaktig gränsuppdatering: om du glömmer +1 eller -1 skapas en oändlig loop när lo == hi. För det tredje, att arbeta på en osorterad array: binärsökning är bara korrekt på sorterade data.
Innan du skriver en binärsökning ska du säga högt: 'Arrayen är sorterad, mina gränser är inkluderande och min loop körs medan 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 för binärsökning
När du ser ett problem med en sorterad array, en monotont växande funktion eller ett sökutrymme som kan halveras bör du genast överväga binärsökning. Berätta hur du tänker under intervjun: 'Eftersom arrayen är sorterad kan jag förkasta hälften av elementen vid varje jämförelse, vilket ger O(log n).'
Kontrollera alltid lösningen med minst tre indata: ett värde i början, ett värde i slutet och ett värde som saknas. Att ange komplexiteten proaktivt – 'tid O(log n), minne O(1)' – innan du blir tillfrågad visar på goda grundkunskaper.
Snabbtest
Testa dina kunskaper om begreppen i Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Sammanfattning av lektionen
I den här lektionen lärde du dig: binärsökning halverar sökutrymmet i varje steg och ger tidskomplexiteten O(log n), den inkluderande gränskonventionen använder lo <= hi med uppdateringarna lo = mid+1 och hi = mid-1, och för att hitta den första eller sista förekomsten fortsätter du söka efter en träff i stället för att returnera direkt. Nästa steg är att utforska hur binärsökning utvidgas till roterade och osorterade arrayer.
Lär dig Python 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
- 30
- Lektioner
- 120
Vanliga frågor
Är lektionen ”Klassisk binärsökning: vänster, höger, mitten” gratis?
Ja – du kan läsa vilka 3 lektioner som helst i lärvägen DSA Interview Prep, inklusive ”Klassisk binärsökning: vänster, höger, mitten”, kostnadsfritt i sin helhet här på webben. Därefter låser CoddyKit PRO upp alla lektioner, plus interaktiv övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Vad lär jag mig i ”Klassisk binärsökning: vänster, höger, mitten”?
Implementera binärsökning iterativt och rekursivt, få koll på off-by-one-detaljer för lo/hi-gränser och verifiera korrektheten med kantfallsindata. Ni övar på DSA Interview Prep 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 DSA Interview Prep?
Du behöver inga förkunskaper. Utbildningen i DSA Interview Prep 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 1 av 4.
Hur lång tid tar lektionen ”Klassisk binärsökning: vänster, höger, mitten”?
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 DSA Interview Prep-lektionen?
Ja. Varje DSA Interview Prep-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