Første True: binærsøk på predikat
Søk etter en monoton ja/nei-grense
Første True: binærsøk på predikat er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 3 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Søk etter en ja/nei-grense
Mange problemer skjuler et monotont predikat: false, false, og deretter true for alltid. Binærsøk kan finne den første true uten en sortert array.
# FFFFTTTT -> find first THva monoton betyr
Et predikat er monotont når det forblir true etter at det først blir true. Det er denne ene egenskapen som gjør det mulig å bruke binærsøk på grensen.
def ok(x):
return x * x >= targetAvgrens svarområdet
Velg et område som sikkert inneholder grensen. Sett low til den minste kandidaten og high til en verdi der ok sikkert er true.
low, high = 0, 10**9Test midtpunktet
Ta mid og kall ok(mid). Det boolske resultatet forteller hvilken halvdel som skal beholdes, akkurat som når en verdi sammenlignes i vanlig binærsøk.
mid = (low + high) // 2
if ok(mid):
...True betyr kanskje mindre
Hvis ok(mid) er true, er mid et gyldig svar, men en mindre verdi kan også fungere. Behold mid ved å sette high = mid, ikke mid - 1.
if ok(mid):
high = midFalse betyr at De må høyere
Hvis ok(mid) er false, ligger grensen over mid. Forkast mid og alt under den med low = mid + 1.
else:
low = mid + 1Kjør løkken så lenge low er mindre enn high
Bruk while low < high, ikke mindre enn eller lik. De to pekerne konvergerer mot den første true-indeksen, og deretter stopper løkken.
while low < high:
mid = (low + high) // 2Svaret er low
Når løkken avsluttes, er low lik high, og begge peker på den første true-verdien. Returner low som grensen De lette etter.
return low # first x where ok(x)Derfor fungerer high = mid
Fordi mid kan være svaret, må De ikke hoppe over den. Bruk av high = mid beholder den i området samtidig som området blir mindre, noe som garanterer fremdrift.
high = mid # mid stays a candidateEksempel: heltallsroten
For å finne den største x der x*x er høyst n, søker De etter den første true-verdien for x*x > n og går deretter ett trinn tilbake. Mønsteret kan brukes på nytt.
def ok(x):
return x * x > n
# answer is found_index - 1Én mal, mange problemer
Denne first-true-malen løser utallige oppgaver: minste gjennomførbare verdi, venstre ytterindeks og minste kapasitet. Lær den én gang, og bruk den overalt.
# low<high, ok->high=mid, else low=mid+1Rask kontroll
Finn steget som holder kandidaten med i søket.
Oppsummering: Finn den første true
De kan nå gjøre et problem om til et monotont predikat og bruke binærsøk på grensen. high = mid sammen med while low < high er det trygge mønsteret. 🧭
Lær deg Forberedelse til kodeintervjuer 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
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Første True: binærsøk på predikat» gratis?
Ja – hele teksten i «Første True: binærsøk på predikat» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Første True: binærsøk på predikat»?
Søk etter en monoton ja/nei-grense Du øver på Forberedelse til kodeintervjuer 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 Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer 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 3 av 4.
Hvor lang tid tar leksjonen «Første True: binærsøk på predikat»?
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 Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-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 uten feil
- bisect_left og bisect_right
- Første True: binærsøk på predikat
- Binærsøk på svaret