Untere und obere Grenze
Implementieren Sie bisect_left und bisect_right von Grund auf und wenden Sie sie anschließend an, um die erste und letzte Position eines Zielwerts zu finden.
Untere und obere Grenze ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 3 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 DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was sind Lower Bound und Upper Bound?
Der Lower Bound eines Zielwerts in einem sortierten Array ist der Index des ersten Elements, das größer oder gleich dem Zielwert ist (oft bisect_left genannt). Der Upper Bound ist der Index des ersten Elements, das strikt größer als der Zielwert ist (bisect_right). Zusammen grenzen sie alle Vorkommen des Zielwerts ein und ermöglichen Bereichsabfragen in O(log n).
Diese beiden Operationen bilden die Grundlage für viele Aufgaben im Vorstellungsgespräch: Vorkommen zählen, einen Bereich finden, die Einfügeposition bestimmen und mehr.
arr = [1, 2, 2, 2, 3, 5]
# lower bound of 2 => index 1 (first element >= 2)
# upper bound of 2 => index 4 (first element > 2)
# occurrences of 2 => upper - lower = 4 - 1 = 3
print('lower bound of 2:', 1)
print('upper bound of 2:', 4)
print('count of 2:', 4 - 1)Lower Bound implementieren (bisect_left)
bisect_left(arr, x) gibt den am weitesten links liegenden Index i zurück, für den arr[i] >= x gilt, oder len(arr), wenn alle Elemente kleiner sind. Die Implementierung verwendet eine exklusive obere Grenze: hi = len(arr), die Schleifenbedingung lo < hi und die Aktualisierung hi = mid, wenn arr[mid] >= x gilt. Dadurch konvergiert das Ergebnis zur am weitesten links liegenden gültigen Position.
def bisect_left(arr, x):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < x:
lo = mid + 1
else:
hi = mid # arr[mid] >= x, so potential answer
return lo # lo == hi == insertion point
arr = [1, 2, 2, 2, 3, 5]
print(bisect_left(arr, 2)) # 1
print(bisect_left(arr, 0)) # 0 (before all)
print(bisect_left(arr, 6)) # 6 (after all)
print(bisect_left(arr, 3)) # 4Upper Bound implementieren (bisect_right)
bisect_right(arr, x) gibt den am weitesten links liegenden Index i zurück, für den arr[i] > x gilt. Nur eine Zeile unterscheidet sich von bisect_left: Die Bedingung ändert sich von arr[mid] < x zu arr[mid] <= x. Wenn arr[mid] <= x gilt, liegt die gesuchte Position strikt rechts von mid, daher setzen wir lo = mid + 1; andernfalls grenzen wir den Bereich von rechts ein.
def bisect_right(arr, x):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= x:
lo = mid + 1 # arr[mid] <= x, so answer is strictly right
else:
hi = mid
return lo
arr = [1, 2, 2, 2, 3, 5]
print(bisect_right(arr, 2)) # 4
print(bisect_right(arr, 0)) # 0
print(bisect_right(arr, 5)) # 6
print(bisect_right(arr, 4)) # 5Vorkommen mit beiden Bounds zählen
Um die Vorkommen eines Zielwerts in einem sortierten Array in O(log n) zu zählen, wenden Sie beide Bounds an: count = bisect_right(arr, target) - bisect_left(arr, target). Wenn count 0 ist, kommt der Zielwert nicht vor. Das ist deutlich schneller als ein linearer Durchlauf und der Standardansatz für Häufigkeitsabfragen in sortierten Daten.
import bisect
def count_occurrences(arr, target):
left = bisect.bisect_left(arr, target)
right = bisect.bisect_right(arr, target)
return right - left
arr = [1, 2, 2, 2, 3, 3, 5]
print(count_occurrences(arr, 2)) # 3
print(count_occurrences(arr, 3)) # 2
print(count_occurrences(arr, 4)) # 0
print(count_occurrences(arr, 1)) # 1Erste und letzte Position des Zielwerts finden
LeetCode 34 „Find First and Last Position of Element in Sorted Array“ verlangt, [first_idx, last_idx] in O(log n) zurückzugeben. Die erste Position ist bisect_left(arr, target) — allerdings nur, wenn arr[result] == target gilt. Die letzte Position ist bisect_right(arr, target) - 1. Wenn eine der beiden Prüfungen fehlschlägt, geben Sie [-1, -1] zurück.
import bisect
def search_range(nums, target):
left = bisect.bisect_left(nums, target)
if left == len(nums) or nums[left] != target:
return [-1, -1]
right = bisect.bisect_right(nums, target) - 1
return [left, right]
print(search_range([5,7,7,8,8,10], 8)) # [3, 4]
print(search_range([5,7,7,8,8,10], 6)) # [-1, -1]
print(search_range([], 0)) # [-1, -1]Einfügeposition (LeetCode 35)
LeetCode 35 „Search Insert Position“ fragt: An welcher Stelle würde der Zielwert eingefügt, damit das Array sortiert bleibt? Das ist genau bisect_left(arr, target). Wenn der Zielwert vorhanden ist, gibt bisect_left seinen Index zurück. Wenn er nicht vorhanden ist, gibt bisect_left den Index zurück, an dem er eingefügt würde. Es ist keine Sonderbehandlung erforderlich — dieselbe Funktion behandelt beide Situationen.
import bisect
def searchInsert(nums, target):
return bisect.bisect_left(nums, target)
print(searchInsert([1,3,5,6], 5)) # 2 (exists at index 2)
print(searchInsert([1,3,5,6], 2)) # 1 (would insert between 1 and 3)
print(searchInsert([1,3,5,6], 7)) # 4 (would append at end)
print(searchInsert([1,3,5,6], 0)) # 0 (would prepend)Der Unterschied zwischen bisect_left und bisect_right
Wenn keine Duplikate vorhanden sind, geben bisect_left und bisect_right denselben Index zurück. Der Unterschied ist nur relevant, wenn der Zielwert mehrfach vorkommt. bisect_left zeigt auf das erste Vorkommen; bisect_right zeigt auf die Position direkt hinter dem letzten Vorkommen. Wählen Sie immer anhand dessen, ob Sie vor den vorhandenen Vorkommen (links) oder danach (rechts) einfügen möchten.
import bisect
arr = [1, 2, 2, 2, 3]
# Insert a new 2 before all existing 2s
print(bisect.bisect_left(arr, 2)) # 1
# Insert a new 2 after all existing 2s
print(bisect.bisect_right(arr, 2)) # 4
# For a value not in array, both give same insertion point
print(bisect.bisect_left(arr, 2.5)) # 4
print(bisect.bisect_right(arr, 2.5)) # 4Bounds auf sortierte Häufigkeitsabfragen anwenden
Wenn Sie viele Häufigkeitsabfragen für Bereiche in einem sortierten Array effizient beantworten müssen, sortieren Sie das Array einmal vor und verwenden Sie für jede Abfrage bisect. Jede Abfrage beantwortet „Wie viele Elemente liegen in [lo, hi]?“ in O(log n) statt O(n). Dieses Muster tritt bei Aufgaben auf, bei denen nach dem Sortieren Elemente innerhalb eines Wertebereichs gezählt werden.
import bisect
def count_in_range(arr, lo, hi):
'''Count elements in arr with lo <= val <= hi. arr must be sorted.'''
left = bisect.bisect_left(arr, lo)
right = bisect.bisect_right(arr, hi)
return right - left
arr = sorted([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
print(arr) # [1,1,2,3,3,4,5,5,5,6,9]
print(count_in_range(arr, 3, 5)) # 6 (3,3,4,5,5,5)
print(count_in_range(arr, 1, 2)) # 3 (1,1,2)Binäre Suche mit benutzerdefiniertem Schlüssel
Manchmal ist der Suchschlüssel nicht der gespeicherte Wert selbst, sondern eine daraus abgeleitete Eigenschaft. Pythons Modul bisect unterstützt keine key-Funktion direkt, aber Sie können die binäre Suche manuell implementieren, indem Sie den Schlüssel innerhalb der Schleife anwenden. Dieses Muster tritt auf, wenn eine Liste von Objekten anhand eines ihrer Attribute durchsucht wird.
# Binary search on a list of (score, name) tuples by score
def lower_bound_by_score(records, min_score):
lo, hi = 0, len(records)
while lo < hi:
mid = lo + (hi - lo) // 2
if records[mid][0] < min_score:
lo = mid + 1
else:
hi = mid
return lo
records = [(50, 'Alice'), (72, 'Bob'), (72, 'Carol'), (88, 'Dave'), (95, 'Eve')]
idx = lower_bound_by_score(records, 72)
print(idx) # 1 (first record with score >= 72)
print(records[idx:]) # [(72,'Bob'),(72,'Carol'),(88,'Dave'),(95,'Eve')]Häufige Fehler bei Bounds im Vorstellungsgespräch
Der häufigste Fehler besteht darin, die Validierung nach dem Aufruf von bisect_left zu vergessen. Die Funktion gibt immer einen gültigen Einfügeindex zurück, garantiert aber nicht, dass das Element an diesem Index dem Zielwert entspricht. Prüfen Sie immer arr[result] == target, bevor Sie davon ausgehen, dass der Zielwert gefunden wurde.
Ein zweiter Fehler besteht darin, bisect_right zu verwenden, wenn Sie das erste Vorkommen suchen — bisect_right gibt die Position direkt hinter dem letzten Vorkommen zurück. Wenn Sie 1 subtrahieren, erhalten Sie also das letzte und nicht das erste Vorkommen.
import bisect
arr = [1, 3, 5, 7]
target = 4
# bisect_left returns 2 (insertion point for 4 between 3 and 5)
idx = bisect.bisect_left(arr, target)
print(idx) # 2
# Validate: arr[2] is 5, not 4 => target absent
found = idx < len(arr) and arr[idx] == target
print('Found:', found) # FalseZusammenfassung: Wann Sie bisect_left und bisect_right verwenden
Verwenden Sie bisect_left, wenn Sie Folgendes benötigen: das erste Vorkommen des Zielwerts, die Einfügeposition, durch die vorhandene Vorkommen nach rechts verschoben werden, oder eine Prüfung, ob der Zielwert vorhanden ist. Verwenden Sie bisect_right, wenn Sie Folgendes benötigen: die Position direkt hinter dem letzten Vorkommen, die Einfügeposition nach allen vorhandenen Vorkommen oder die Anzahl der Elemente <= target (sie entspricht bisect_right(arr, target)).
Beide Verfahren laufen in O(log n) und sind Teil der Python-Standardbibliothek. Sie können sie daher direkt importieren und verwenden, sofern der Interviewer Sie nicht auffordert, sie von Grund auf zu implementieren.
Kurzer Test
Testen Sie Ihr Verständnis der Konzepte aus dieser Lektion zu Data Structures & Algorithms — Coding Interview Prep.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: bisect_left findet das erste Element >= target, bisect_right findet das erste Element > target (direkt hinter dem letzten Vorkommen) und ihre Differenz liefert die Anzahl der Vorkommen in O(log n). Als Nächstes sehen wir uns die binäre Suche im Lösungsraum an, bei der der Suchraum aus einem Bereich möglicher Antworten und nicht aus einem Array-Index besteht.
Häufig gestellte Fragen
Ist die Lektion „Untere und obere Grenze“ kostenlos?
Ja — der vollständige Text von „Untere und obere Grenze“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Untere und obere Grenze“?
Implementieren Sie bisect_left und bisect_right von Grund auf und wenden Sie sie anschließend an, um die erste und letzte Position eines Zielwerts zu finden. Du übst DSA Interview Prep 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 DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep 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 3 von 4.
Wie lange dauert die Lektion „Untere und obere Grenze“?
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 DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-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: links, rechts, Mitte
- Binäre Suche in rotierten und unsortierten Arrays
- Untere und obere Grenze
- Binäre Suche im Lösungsraum