Klassinen binäärihaku: vasen, oikea, keskikohta
Toteuttakaa binäärihaku iteroivasti ja rekursiivisesti, hallitkaa lo- ja hi-rajojen off-by-one-yksityiskohdat ja varmistakaa oikeellisuus reuna-arvotapauksilla.
Klassinen binäärihaku: vasen, oikea, keskikohta on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 1/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Miksi binäärihaku on tärkeä
Binäärihaku pienentää lineaarisen haun aikavaativuuden O(n):stä O(log n):ään puolittamalla hakutilan jokaisella askeleella. Miljoonan alkion taulukossa lineaarinen haku vaatii enintään 1 000 000 vertailua, mutta binäänihaku enintään 20. Tämän tehokkuuden ansiosta se on yksi koodaushaastattelujen yleisimmin testatuista algoritmeista.
Keskeinen oivallus on, että lajitellun taulukon ansiosta voitte yhden vertailun jälkeen päättää, kumman puolikkaan jäljellä olevista tiedoista voitte hylätä kokonaan.
Vasen–keski–oikea-malli
Binäärihaussa käytetään kolmea indeksiosoitinta: lo (vasen raja), hi (oikea raja) ja mid (keskikohta). Jokaisella kierroksella lasketaan mid = (lo + hi) // 2 ja verrataan kohdetta arvoon arr[mid]. Jos kohde on pienempi, siirtäkää rajaa komennolla hi = mid - 1; jos se on suurempi, siirtäkää rajaa komennolla lo = mid + 1; jos arvot ovat yhtä suuret, kohde löytyi.
Silmukka jatkuu niin kauan kuin lo <= hi. Jos silmukka päättyy löytämättä kohdetta, palauttakaa -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)) # -1Kokonaislukujen ylivuodon välttäminen mid-arvossa
Lauseke mid = (lo + hi) // 2 voi aiheuttaa kokonaislukujen ylivuodon kielissä, joissa kokonaisluvuilla on kiinteä leveys (Java, C++). Pythonin kokonaisluvut käyttävät mielivaltaista tarkkuutta, joten ylivuotoa ei koskaan tapahdu, mutta haastattelijat odottavat silti, että tunnette turvallisen vaihtoehdon: mid = lo + (hi - lo) // 2.
Tämä muoto laskee saman keskikohdan, mutta lisää lo-arvoon vain puolikkaan etäisyyden sen sijaan, että osoittimet laskettaisiin ensin yhteen. Tämän mainitseminen haastattelussa osoittaa, että ymmärrätte matalan tason näkökohdat.
# 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) # TrueMukaan lukevat ja poissulkevat rajat
Yksi binäärihaun haastavimmista kohdista on päättää, osoittaako hi viimeiseen kelvolliseen indeksiin (mukaan lukien, hi = len(arr) - 1) vai taulukon lopun jälkeiseen ensimmäiseen indeksiin (poissulkeva raja, hi = len(arr)). Eri käytännöt edellyttävät erilaisia silmukan ehtoja ja rajojen päivityksiä.
Käyttäkää mukaan lukevien rajojen kanssa ehtoa while lo <= hi ja päivittäkää rajaa komennolla hi = mid - 1. Käyttäkää poissulkevien rajojen kanssa ehtoa while lo < hi ja päivittäkää rajaa komennolla hi = mid. Käytäntöjen sekoittaminen on yleisin binäärihaun toteutusten virhelähde.
# 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)) # 2Rekursiivinen binäärihaku
Binäärihaku voidaan kirjoittaa rekursiivisesti välittämällä päivitetyt lo- ja hi-rajat kutsupinon kautta. Jokainen rekursiivinen kutsu puolittaa hakutilan, joten syvyys on O(log n). Perustapaus saavutetaan, kun lo > hi (kohdetta ei löytynyt) tai arr[mid] == target (kohde löytyi).
Tuotantokoodissa suositaan iteroivaa versiota, koska se välttää kutsukehysten aiheuttaman lisäkustannuksen, mutta rekursiivinen versio havainnollistaa hajota ja hallitse -rakenteen selkeämmin taululla.
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)) # 4Reunatapaukset: tyhjä taulukko, yksi alkio
Vankan binäärihaun on käsiteltävä reunatapaukset kaatumatta. Kolme yleisintä tapausta ovat tyhjä taulukko (silmukka ei suoritu koskaan ja -1 palautetaan oikein), yhden alkion taulukko (mid, lo ja hi ovat samat, joten yksi vertailu riittää) sekä alueen ulkopuolella olevat kohteet (lo ylittää lopulta hi:n ja -1 palautetaan).
Tarkistakaa toteutuksenne aina näillä syötteillä ennen kuin siirrytte haastattelun jatkokysymyksiin.
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)Aika- ja tilavaativuus
Binäärihaun O(log n):n aikavaativuus johtuu siitä, että jokainen vertailu puolittaa hakutilan. K:n vertailun jälkeen jäljellä oleva tila on n/2^k; haku päättyy, kun tämä saavuttaa arvon 1, joten k = log₂ n.
Tilavaativuus on iteroivassa versiossa O(1) (vain kolme kokonaislukumuuttujaa) ja rekursiivisessa versiossa O(log n) kutsupinon syvyyden vuoksi. Ilmoittakaa haastattelussa aina molemmat ja suosikaa iteroivaa versiota, kun tilaa on rajoitetusti.
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}')Tarkan osuman ja rajan etsiminen
Perinteinen binäärihaku palauttaa minkä tahansa indeksin, jossa kohde esiintyy. Monissa haastattelutehtävissä pyydetään kuitenkin kohteen ensimmäistä tai viimeistä esiintymää. Tällöin hakua on jatkettava osuman löytymisen jälkeenkin: älkää palauttako heti, vaan siirtäkää rajaa ja jatkakaa hakua.
Kun etsitte ensimmäistä esiintymää ja löydätte ehdon arr[mid] == target, tallentakaa mid ehdokkaaksi ja asettakaa hi = mid - 1. Viimeistä esiintymää etsiessänne asettakaa 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)) # 1Pythonin bisect-moduulin käyttäminen
Pythonin vakiokirjasto tarjoaa tuotantokäyttöön valmiit binäärihaut bisect.bisect_left(arr, x) ja bisect.bisect_right(arr, x). bisect_left palauttaa vasemmanpuoleisimman indeksin, johon x voidaan lisätä niin, että taulukko pysyy lajiteltuna. Käytännössä se etsii ensimmäisen kohdan, jossa arr[i] >= x.
Haastattelijat saattavat sallia bisect-moduulin käytön; varmistakaa tämä aina ensin. On silti tärkeää tietää, miten se toimii konepellin alla (kyseessä on O(log n):n binäärihaku).
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) # TrueBinäärihaun yleiset sudenkuopat
Kolme virhettä aiheuttaa suurimman osan binäärihaun ongelmista haastatteluissa. Ensimmäinen on väärä silmukan ehto: merkin < käyttäminen merkin <= sijaan mukaan lukevien rajojen kanssa ohittaa viimeisen jäljellä olevan alkion. Toinen on virheellinen rajojen päivitys: +1- tai -1-osan unohtaminen aiheuttaa ikuisen silmukan, kun lo == hi. Kolmas on lajittelemattoman taulukon käsittely: binäärihaku toimii oikein vain lajitellulla datalla.
Sanokaa ennen binäärihaun kirjoittamista ääneen: 'Taulukko on lajiteltu, rajani sisältävät rajakohdat ja silmukkani suoritetaan, kun 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)Binäärihaun haastatteluvinkit
Kun näette tehtävän, jossa käsitellään lajiteltua taulukkoa, monotonisesti kasvavaa funktiota tai hakutilaa, joka voidaan puolittaa, harkitkaa heti binäärihakua. Kertokaa haastattelussa ajattelunne: 'Koska taulukko on lajiteltu, voin hylätä puolet alkioista jokaisella vertailulla, joten aikavaativuus on O(log n).'
Tarkistakaa ratkaisunne aina vähintään kolmella syötteellä: arvolla alussa, arvolla lopussa ja arvolla, jota ei esiinny. Aikavaativuuden ilmoittaminen oma-aloitteisesti — 'aika O(log n), tila O(1)' — ennen kuin sitä kysytään osoittaa vahvaa perusosaamista.
Pikatarkistus
Testatkaa tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -aiheen käsitteiden ymmärtämistä.
Oppitunnin yhteenveto
Tässä oppitunnissa opitte, että binäärihaku puolittaa hakutilan jokaisella askeleella, joten aikavaativuus on O(log n), mukaan lukevien rajojen käytäntö käyttää ehtoa lo <= hi ja päivityksiä lo = mid+1 sekä hi = mid-1 ja ensimmäisten tai viimeisten esiintymien löytämiseksi hakua jatketaan osuman jälkeen sen sijaan, että palautettaisiin heti. Seuraavaksi tutustumme siihen, miten binäärihakua laajennetaan kierrolla siirrettyihin ja lajittelemattomiin taulukoihin.
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Klassinen binäärihaku: vasen, oikea, keskikohta” ilmainen?
Kyllä – oppitunnin ”Klassinen binäärihaku: vasen, oikea, keskikohta” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Klassinen binäärihaku: vasen, oikea, keskikohta”?
Toteuttakaa binäärihaku iteroivasti ja rekursiivisesti, hallitkaa lo- ja hi-rajojen off-by-one-yksityiskohdat ja varmistakaa oikeellisuus reuna-arvotapauksilla. Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 1/4.
Kuinka kauan ”Klassinen binäärihaku: vasen, oikea, keskikohta”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Klassinen binäärihaku: vasen, oikea, keskikohta
- Binäärihaku käännetyistä ja järjestämättömistä taulukoista
- Alaraja ja yläraja
- Vastausavaruuden binäärihaku