bisect_left og bisect_right
Finn innsettingspunkter i en sortert liste
bisect_left og bisect_right er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 2 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 uten standardkoden
Pythons bisect-modul gir Dem et ferdigtestet binærsøk for sorterte lister. En løkke som ikke er skrevet for hånd, betyr ingen off-by-one-feil å feilsøke.
import bisectInnsettingspunkter, ikke boolske verdier
I stedet for true eller false returnerer bisect en indeks der en verdi kan settes inn for å beholde listen sortert. Det er denne indeksen som er den virkelige styrken.
a = [1, 3, 3, 3, 7]bisect_left heller mot venstre
bisect_left returnerer den første posisjonen der verdien kan settes inn. Ved duplikater havner den før alle like elementer, aldri etter dem.
bisect.bisect_left(a, 3) # 1bisect_right heller mot høyre
bisect_right returnerer posisjonen rett etter det siste like elementet. Ved duplikater havner den etter alle samsvarende verdier.
bisect.bisect_right(a, 3) # 4Tell like elementer
Trekk de to fra hverandre for å telle duplikater av en verdi i O(log n). right minus left gir nøyaktig hvor mange ganger den forekommer.
lo = bisect.bisect_left(a, 3)
hi = bisect.bisect_right(a, 3)
print(hi - lo) # 3Fantes verdien?
For å kontrollere medlemskap henter De i fra bisect_left og bekrefter at a[i] er lik target. Kontroller først at i ikke har nådd listelengden.
i = bisect.bisect_left(a, x)
found = i < len(a) and a[i] == xFørste element som er minst x
bisect_left finner også det første elementet som er større enn eller lik x. Denne indeksen peker direkte på svaret for nedre grense.
i = bisect.bisect_left(a, x) # first >= xFørste element som er større enn x
Trenger De det første elementet som er strengt større enn x? bisect_right gir denne indeksen direkte, som den øvre grensen.
i = bisect.bisect_right(a, x) # first > xSett inn og behold sorteringen
insort finner plassen og setter inn elementet i ett kall, samtidig som listen forblir sortert. Det er praktisk når De bygger en sortert struktur fortløpende.
bisect.insort(a, 5) # a stays sortedSøk i et avgrenset område
Valgfrie lo og hi-argumenter begrenser søket til et utsnitt. Dermed unngår De kopiering når De bare trenger et delområde.
bisect.bisect_left(a, x, 2, 5)Nøkler via en hjelpeliste
bisect sammenligner hele elementer. For å søke etter et felt kan De derfor bygge en parallell liste med bare disse nøklene og bruke bisect på den i stedet.
keys = [p[0] for p in pairs]
i = bisect.bisect_left(keys, target)Rask kontroll
Resonner om duplikater og innsettingspunkter.
Oppsummering: Bli ekspert på bisect
De kan nå finne innsettingspunkter, telle duplikater og finne nedre og øvre grenser på logaritmisk tid. Bruk bisect før De skriver en løkke. ✨
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 «bisect_left og bisect_right» gratis?
Ja – hele teksten i «bisect_left og bisect_right» 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 «bisect_left og bisect_right»?
Finn innsettingspunkter i en sortert liste 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 2 av 4.
Hvor lang tid tar leksjonen «bisect_left og bisect_right»?
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