bisect_left und bisect_right
Finden Sie Einfügepositionen in einer sortierten Liste
bisect_left und bisect_right ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Suchen ohne Standardcode
Pythons Modul bisect bietet eine getestete binäre Suche für sortierte Listen. Eine handgeschriebene Schleife bedeutet, dass Sie keine Off-by-one-Fehler debuggen müssen.
import bisectEinfügepositionen statt boolescher Werte
Statt true oder false gibt bisect einen Index zurück, an dem ein Wert eingefügt werden kann, damit die Liste sortiert bleibt. Darin liegt die eigentliche Stärke.
a = [1, 3, 3, 3, 7]bisect_left sucht eher links
bisect_left gibt die erste Position zurück, an der der Wert eingefügt werden könnte. Bei Duplikaten liegt sie vor allen gleichen Elementen, niemals dahinter.
bisect.bisect_left(a, 3) # 1bisect_right sucht eher rechts
bisect_right gibt die Position direkt hinter dem letzten gleichen Element zurück. Bei Duplikaten liegt sie hinter jedem passenden Wert.
bisect.bisect_right(a, 3) # 4Gleiche Elemente zählen
Subtrahieren Sie die beiden Werte, um Duplikate eines Werts in O(log n) zu zählen. right minus left ergibt genau, wie oft er vorkommt.
lo = bisect.bisect_left(a, 3)
hi = bisect.bisect_right(a, 3)
print(hi - lo) # 3War der Wert vorhanden?
Um die Zugehörigkeit zu prüfen, holen Sie i mit bisect_left und bestätigen, dass a[i] dem target entspricht. Stellen Sie zuerst sicher, dass i nicht die Länge der Liste erreicht.
i = bisect.bisect_left(a, x)
found = i < len(a) and a[i] == xErstes Element mindestens X
bisect_left findet auch das erste Element, das größer oder gleich x ist. Dieser Index zeigt direkt auf die gesuchte untere Schranke.
i = bisect.bisect_left(a, x) # first >= xErstes Element strikt größer
Benötigen Sie das erste Element, das strikt größer als x ist? bisect_right liefert diesen Index direkt – das Gegenstück zur oberen Schranke.
i = bisect.bisect_right(a, x) # first > xEinfügen und sortiert bleiben
insort findet die richtige Stelle und fügt das Element in einem Aufruf ein, sodass die Liste geordnet bleibt. Das ist praktisch, wenn Sie eine sortierte Struktur laufend aufbauen.
bisect.insort(a, 5) # a stays sortedIn einem Bereich suchen
Mit den optionalen Argumenten lo und hi beschränken Sie die Suche auf einen Ausschnitt. So vermeiden Sie Kopien, wenn Sie nur einen Teilbereich benötigen.
bisect.bisect_left(a, x, 2, 5)Schlüssel über eine Hilfsliste
bisect vergleicht ganze Elemente. Um nach einem Feld zu suchen, erstellen Sie daher eine parallele Liste nur mit diesen Schlüsseln und verwenden bisect für diese Liste.
keys = [p[0] for p in pairs]
i = bisect.bisect_left(keys, target)Kurzer Check
Überlegen Sie, wie sich Duplikate und Einfügepositionen verhalten.
Zusammenfassung: Bisect sicher beherrschen
Sie können jetzt Einfügepositionen finden, Duplikate zählen und untere sowie obere Schranken in logarithmischer Zeit bestimmen. Greifen Sie zu bisect, bevor Sie eine Schleife schreiben. ✨
Häufig gestellte Fragen
Ist die Lektion „bisect_left und bisect_right“ kostenlos?
Ja — der vollständige Text von „bisect_left und bisect_right“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „bisect_left und bisect_right“?
Finden Sie Einfügepositionen in einer sortierten Liste Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.
Wie lange dauert die Lektion „bisect_left und bisect_right“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Klassische binäre Suche ohne Fehler
- bisect_left und bisect_right
- First True: binäre Suche nach einem Prädikat
- Binäre Suche nach der Antwort