Klassisk binær søgning uden fejl
Få low-, high- og mid-løkken helt rigtig
Klassisk binær søgning uden fejl er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 1 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.
Halvér søgeområdet
Binær søgning finder en værdi i en sorteret liste ved at halvere området for hvert trin. Det gør en langsom O(n)-gennemgang til en hurtig søgning på O(log n).
a = [1, 3, 5, 7, 9] # must be sortedSortering er den eneste regel
Binær søgning fungerer kun på sorterede data. Hvis listen ikke er sorteret, skal du sortere den først, ellers bliver resultatet meningsløst og forkert.
a.sort() # ascending order requiredTo grænser
Begynd med to pointere: low ved indeks 0 og high ved det sidste indeks. Målet ligger altid mellem dem, hvis det findes.
low, high = 0, len(a) - 1Find midten sikkert
Beregn mid som low + (high - low) // 2. I Python er heltalsoverløb ikke et problem, men denne form er den sikre vane overalt.
mid = low + (high - low) // 2Tre udfald
Sammenlign a[mid] med target. Enten har du fundet det, eller også er det for lille eller for stort. Hvert tilfælde indsnævrer området på sin egen måde.
if a[mid] == target:
return midFor lille, gå mod højre
Hvis a[mid] er mindre end target, må svaret ligge til højre. Flyt low til mid + 1, og kassér den venstre halvdel.
elif a[mid] < target:
low = mid + 1For stort, gå mod venstre
Hvis a[mid] er større end target, skal du søge i den venstre halvdel. Flyt high til mid - 1, så du aldrig undersøger mid igen.
else:
high = mid - 1Løkkens betingelse
Fortsæt while low is less than or equal to high. Når de krydser hinanden, er området tomt, og target findes ikke.
while low <= high:
mid = low + (high - low) // 2Meld ikke fundet
Hvis løkken slutter uden et match, mangler værdien. return -1 er konventionen, så kaldere kan skelne mellem succes og fejl.
return -1 # target not in listFælden med én forskydning
Den klassiske fejl er at glemme +1 eller -1, når du flytter en pointer. Hvis du springer det over, bliver mid testet igen for evigt, og løkken bliver uendelig.
low = mid + 1 # not low = midBrug biblioteket, når du kan
Til en almindelig medlemskabstest har Pythons bisect-modul allerede en fejlfri søgning. Skriv kun løkken selv, når du har brug for særlig logik.
import bisect
i = bisect.bisect_left(a, target)Hurtig kontrol
Tænk over, hvad der holder løkken korrekt.
Opsummering: Søg uden fejl
Du kan nu sætte low og high, beregne mid sikkert, indsnævre højre side og undgå fælden med én forskydning. Du har nu logaritmisk søgning i værktøjskassen. 🎯
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 “Klassisk binær søgning uden fejl” gratis?
Ja — hele teksten til “Klassisk binær søgning uden fejl” 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 “Klassisk binær søgning uden fejl”?
Få low-, high- og mid-løkken helt rigtig 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 1 af 4.
Hvor lang tid tager lektionen “Klassisk binær søgning uden fejl”?
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