Ensimmäinen True: predikaattibinäärihaku
Etsi monotoninen kyllä/ei-raja
Ensimmäinen True: predikaattibinäärihaku on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 3/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.
Hae kyllä–ei-rajaa
Monien ongelmien taustalla on monotoninen predikaatti: false, false ja sen jälkeen aina true. Binäärihaku voi löytää ensimmäisen truen ilman järjestettyä taulukkoa.
# FFFFTTTT -> find first TMitä monotonisuus tarkoittaa
Predikaatti on monotoninen, kun se muuttuu true-arvoksi ja pysyy sen jälkeen true-arvona. Juuri tämä ominaisuus mahdollistaa rajan etsimisen binäärihaulla.
def ok(x):
return x * x >= targetRajaa vastausavaruus
Valitse alue, joka varmasti sisältää rajan. Aseta low pienimmäksi ehdokkaaksi ja high arvoksi, jolla ok on varmasti true.
low, high = 0, 10**9Testaa keskikohta
Ota mid ja kutsu funktiota ok(mid). Totuusarvo kertoo, kumpi puolisko säilytetään, aivan kuten arvon vertailu tavallisessa binäärihaussa.
mid = (low + high) // 2
if ok(mid):
...True tarkoittaa ehkä pienempää
Jos ok(mid) on true, mid on kelvollinen vastaus, mutta pienempikin arvo saattaa toimia. Säilytä mid asettamalla high = mid, älä mid - 1.
if ok(mid):
high = midFalse tarkoittaa siirtymistä suurempaan
Jos ok(mid) on false, raja on mid-arvon yläpuolella. Hylkää mid ja kaikki sitä pienemmät arvot komennolla low = mid + 1.
else:
low = mid + 1Silmukoi, kunnes low alittaa high-arvon
Käytä ehtoa while low < high, älä ehtoa less-than-or-equal. Osoittimet lähestyvät ensimmäistä true-indeksiä, minkä jälkeen silmukka päättyy.
while low < high:
mid = (low + high) // 2Vastaus on low
Kun silmukka päättyy, low on sama kuin high, ja molemmat osoittavat ensimmäiseen true-arvoon. Palauta low etsimänäsi rajana.
return low # first x where ok(x)Miksi high = mid toimii
Koska mid voi olla vastaus, sitä ei saa ohittaa. high = mid pitää sen alueella ja pienentää aluetta silti, mikä takaa etenemisen.
high = mid # mid stays a candidateEsimerkki kokonaisluvun neliöjuuresta
Kun etsit suurinta x:ää, jolla x*x on enintään n, etsi ehdon x*x > n ensimmäinen true-arvo ja pienennä tulosta yhdellä. Sama malli toistuu.
def ok(x):
return x * x > n
# answer is found_index - 1Yksi malli, monia ongelmia
Tämä first-true-malli ratkaisee lukemattomia tehtäviä: pienimmän toteuttamiskelpoisen arvon, vasemmanpuoleisimman indeksin ja pienimmän kapasiteetin etsimisen. Opettele se kerran ja käytä kaikkialla.
# low<high, ok->high=mid, else low=mid+1Pikatarkistus
Selvitä siirto, joka pitää ehdokkaan mukana.
Kertaus: Ensimmäinen true löytyi
Osaat nyt muuttaa ongelman monotoniseksi predikaatiksi ja etsiä rajan binäärihaulla. high = mid yhdessä ehdon while low < high kanssa on turvallinen malli. 🧭
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 ”Ensimmäinen True: predikaattibinäärihaku” ilmainen?
Kyllä – oppitunnin ”Ensimmäinen True: predikaattibinäärihaku” 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 ”Ensimmäinen True: predikaattibinäärihaku”?
Etsi monotoninen kyllä/ei-raja 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 3/4.
Kuinka kauan ”Ensimmäinen True: predikaattibinäärihaku”-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 ilman virheitä
- bisect_left ja bisect_right
- Ensimmäinen True: predikaattibinäärihaku
- Binäärihaku vastauksesta