bisect_left og bisect_right
Find indsættelsespositioner i en sorteret liste
bisect_left og bisect_right er en gratis Competitive Programming Academy-lektion på CoddyKit. Dette er lektion 2 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 Competitive Programming Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Competitive Programming Academy-kurset indeholder 4 lektioner i alt.
Søg uden standardkoden
Pythons bisect-modul giver dig en gennemtestet binær søgning i sorterede lister. Uden en håndskrevet løkke er der ingen fejl med én forskydning, du skal fejlfinde.
import bisectIndsættelsespunkter, ikke boolske værdier
I stedet for sandt eller falsk returnerer bisect et indeks, hvor en værdi kan indsættes, så listen forbliver sorteret. Det indeks er den egentlige styrke.
a = [1, 3, 3, 3, 7]bisect_left går mod venstre
bisect_left returnerer den første position, hvor værdien kan indsættes. Ved dubletter lander den før alle ens elementer, aldrig efter dem.
bisect.bisect_left(a, 3) # 1bisect_right går mod højre
bisect_right returnerer positionen lige efter det sidste ens element. Ved dubletter lander den efter alle matchende værdier.
bisect.bisect_right(a, 3) # 4Tæl ens elementer
Træk de to fra hinanden for at tælle dubletter af en værdi på O(log n). right minus left giver præcis, hvor mange gange værdien forekommer.
lo = bisect.bisect_left(a, 3)
hi = bisect.bisect_right(a, 3)
print(hi - lo) # 3Fandtes værdien?
For at kontrollere medlemskab skal du hente i fra bisect_left og bekræfte, at a[i] er lig med target. Kontrollér først, at i ikke når listens længde.
i = bisect.bisect_left(a, x)
found = i < len(a) and a[i] == xFørste element mindst X
bisect_left finder også det første element, der er større end eller lig med x. Det indeks peger direkte på svaret for den nedre grænse.
i = bisect.bisect_left(a, x) # first >= xFørste element strengt større
Har du brug for det første element, der er strengt større end x? bisect_right giver dette indeks direkte, som den øvre grænse.
i = bisect.bisect_right(a, x) # first > xIndsæt, og bevar sorteringen
insort finder pladsen og indsætter i ét kald, så listen forbliver sorteret. Det er praktisk, når du bygger en sorteret datastruktur løbende.
bisect.insort(a, 5) # a stays sortedSøg i et vindue
De valgfrie argumenter lo og hi begrænser søgningen til et udsnit. Det undgår kopiering, når du kun interesserer dig for et delområde.
bisect.bisect_left(a, x, 2, 5)Nøgler via en hjælpeliste
bisect sammenligner hele elementer, så hvis du vil søge efter et felt, skal du opbygge en parallel liste med kun disse nøgler og bruge bisect på den i stedet.
keys = [p[0] for p in pairs]
i = bisect.bisect_left(keys, target)Hurtig kontrol
Overvej dubletter og indsættelsespunkter.
Opsummering: Få styr på bisect
Du kan nu finde indsættelsespunkter, tælle dubletter og finde nedre og øvre grænser på logaritmisk tid. Brug bisect, før du skriver en løkke. ✨
Lær Python 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
- 30
- Lektioner
- 120
Ofte stillede spørgsmål
Er lektionen “bisect_left og bisect_right” gratis?
Ja — hele teksten til “bisect_left og bisect_right” 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 Competitive Programming Academy-kurset, skal du opgradere til CoddyKit PRO. Competitive Programming Academy-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “bisect_left og bisect_right”?
Find indsættelsespositioner i en sorteret liste Du øver dig i Competitive Programming Academy 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å Competitive Programming Academy?
Der kræves ingen tidligere erfaring. Competitive Programming Academy 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 2 af 4.
Hvor lang tid tager lektionen “bisect_left og bisect_right”?
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 Competitive Programming Academy-lektion?
Ja. Alle Competitive Programming Academy-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