Klassinen binäärihaku ilman virheitä
Hallitse low-, high- ja mid-silmukka
Klassinen binäärihaku ilman virheitä on ilmainen Competitive Programming Academy-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 Competitive Programming Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Competitive Programming Academy-kurssilla on yhteensä 4 oppituntia.
Puolita hakualue
Binäärihaku löytää arvon järjestetystä listasta puolittamalla alueen jokaisella kierroksella. Hidas O(n)-läpikäynti muuttuu näin nopeaksi O(log n)-hauksi.
a = [1, 3, 5, 7, 9] # must be sortedJärjestys on ainoa ehto
Binäärihaku toimii vain järjestetyllä datalla. Jos lista ei ole järjestyksessä, järjestä se ensin, tai tulos on merkityksetön ja väärä.
a.sort() # ascending order requiredKaksi rajaa
Aloita kahdella osoittimella: low indeksissä 0 ja high viimeisessä indeksissä. Jos tavoite on olemassa, se on aina niiden välissä.
low, high = 0, len(a) - 1Etsi keskikohta turvallisesti
Laske mid muodossa low + (high - low) // 2. Pythonissa ylivuoto ei ole ongelma, mutta tämä muoto on turvallinen tapa kaikkialla.
mid = low + (high - low) // 2Kolme lopputulosta
Vertaa a[mid]-arvoa tavoitteeseen. Joko löysit sen, arvo on liian pieni tai se on liian suuri. Jokainen tapaus pienentää aluetta eri tavalla.
if a[mid] == target:
return midLiian pieni, siirry oikealle
Jos a[mid] on tavoitetta pienempi, vastaus on oltava oikealla. Siirrä low kohtaan mid + 1 ja hylkää vasen puolisko.
elif a[mid] < target:
low = mid + 1Liian suuri, siirry vasemmalle
Jos a[mid] on tavoitetta suurempi, hae vasemmasta puoliskosta. Siirrä high kohtaan mid - 1, jotta et tarkista mid-arvoa enää uudelleen.
else:
high = mid - 1Silmukan ehto
Jatka while low is less than or equal to high -ehdon vallitessa. Kun osoittimet ohittavat toisensa, alue on tyhjä eikä tavoitetta ole.
while low <= high:
mid = low + (high - low) // 2Ilmoita, ettei arvoa löydy
Jos silmukka päättyy ilman osumaa, arvo puuttuu. Palauta -1 tavan mukaan, jotta kutsuja erottaa onnistumisen epäonnistumisesta.
return -1 # target not in listYhden poikkeaman ansa
Klassinen virhe on unohtaa +1 tai -1 osoitinta siirrettäessä. Jos jätät sen pois, mid tarkistetaan ikuisesti uudelleen ja syntyy ääretön silmukka.
low = mid + 1 # not low = midKäytä kirjastoa, kun voit
Pelkkään jäsenyyden testaamiseen Pythonin bisect-moduuli tarjoaa valmiin, virheettömän haun. Kirjoita silmukka itse vain, jos tarvitset mukautettua logiikkaa.
import bisect
i = bisect.bisect_left(a, target)Pikatarkistus
Mieti, mikä pitää silmukan oikeellisena.
Kertaus: Hae ilman virheitä
Osaat nyt asettaa arvot low ja high, laskea mid-arvon turvallisesti, pienentää oikeaa puolta ja välttää yhden poikkeaman ansan. Logaritminen haku on hallussasi. 🎯
Opi Python 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
- 30
- Oppitunnit
- 120
Usein kysytyt kysymykset
Onko oppitunti ”Klassinen binäärihaku ilman virheitä” ilmainen?
Kyllä – oppitunnin ”Klassinen binäärihaku ilman virheitä” 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 Competitive Programming Academy-kurssin, päivitä CoddyKit PROhon. Competitive Programming Academy-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Klassinen binäärihaku ilman virheitä”?
Hallitse low-, high- ja mid-silmukka Harjoittelet Competitive Programming Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Competitive Programming Academy-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Competitive Programming Academy-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 ilman virheitä”-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ä Competitive Programming Academy-oppitunnilla?
Kyllä. Jokainen Competitive Programming Academy-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 ilman virheitä
- bisect_left ja bisect_right
- Ensimmäinen True: predikaattibinäärihaku
- Binäärihaku vastauksesta