Første True: prædikatbaseret binær søgning
Søg efter en monoton ja/nej-grænse
Første True: prædikatbaseret binær søgning er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Søg efter en ja/nej-grænse
Mange problemer gemmer på et monotont prædikat: falsk, falsk og derefter sandt for altid. Binær søgning kan finde det første sande resultat uden et sorteret array.
# FFFFTTTT -> find first THvad monoton betyder
Et prædikat er monotont, når det bliver ved med at være sandt, efter at det først er blevet sandt. Det er den ene egenskab, der gør det muligt at søge binært efter grænsen.
def ok(x):
return x * x >= targetAfgræns svarområdet
Vælg et område, der med sikkerhed indeholder grænsen. Sæt low til den mindste kandidat og high til en værdi, hvor ok helt sikkert er sandt.
low, high = 0, 10**9Test midten
Tag mid, og kald ok(mid). Det boolske resultat fortæller dig, hvilken halvdel du skal beholde, præcis som når du sammenligner en værdi ved almindelig binær søgning.
mid = (low + high) // 2
if ok(mid):
...Sandt betyder måske mindre
Hvis ok(mid) er sandt, er mid et gyldigt svar, men en mindre værdi kan også fungere. Behold mid ved at sætte high = mid, ikke mid - 1.
if ok(mid):
high = midFalsk betyder, at du skal højere op
Hvis ok(mid) er falsk, ligger grænsen over mid. Kassér mid og alt under det med low = mid + 1.
else:
low = mid + 1Løb, mens low er under high
Brug while low < high, ikke mindre end eller lig med. De to pointere nærmer sig det første sande indeks, hvorefter løkken stopper.
while low < high:
mid = (low + high) // 2Svaret er low
Når løkken slutter, er low lig med high, og begge peger på den første sande værdi. Returnér low som den grænse, du ledte efter.
return low # first x where ok(x)Hvorfor high = mid virker
Fordi mid kan være svaret, må du ikke springe det over. high = mid holder det inden for området, samtidig med at området bliver mindre, så der garanteres fremdrift.
high = mid # mid stays a candidateEksempel på heltalskvadratrod
For at finde det største x, hvor x*x højst er n, skal du søge efter den første sande værdi for x*x > n og derefter gå én tilbage. Mønstret kan genbruges.
def ok(x):
return x * x > n
# answer is found_index - 1Én skabelon, mange problemer
Denne skabelon for første sande løser utallige opgaver: den mindste mulige værdi, det venstrest mulige indeks og den mindste kapacitet. Lær den én gang, og genbrug den overalt.
# low<high, ok->high=mid, else low=mid+1Hurtig kontrol
Find det trin, der holder kandidaten i spil.
Opsummering: Find det første sande
Du kan nu omsætte et problem til et monotont prædikat og søge binært efter grænsen. high = mid sammen med while low < high er det sikre mønster. 🧭
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Første True: prædikatbaseret binær søgning” gratis?
Ja — hele teksten til “Første True: prædikatbaseret binær søgning” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Første True: prædikatbaseret binær søgning”?
Søg efter en monoton ja/nej-grænse Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 3 af 4.
Hvor lang tid tager lektionen “Første True: prædikatbaseret binær søgning”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Klassisk binær søgning uden fejl
- bisect_left og bisect_right
- Første True: prædikatbaseret binær søgning
- Binær søgning på svaret