Limite inferiore e limite superiore
Implementi da zero bisect_left e bisect_right e li applichi per trovare la prima e l'ultima posizione di un valore obiettivo
Limite inferiore e limite superiore è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa sono il lower bound e l'upper bound?
Il lower bound di un valore target in un array ordinato è l'indice del primo elemento maggiore o uguale al target, spesso indicato con bisect_left. L'upper bound è l'indice del primo elemento strettamente maggiore del target (bisect_right). Insieme, delimitano tutte le occorrenze del target e consentono di eseguire query su intervalli in O(log n).
Queste due operazioni sono alla base di molti problemi da colloquio: contare le occorrenze, trovare un intervallo, determinare la posizione di inserimento e altro ancora.
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)Implementare il lower bound (bisect_left)
bisect_left(arr, x) restituisce il primo indice i tale che arr[i] >= x, oppure len(arr) se tutti gli elementi sono più piccoli. L'implementazione utilizza un limite superiore esclusivo: hi = len(arr), condizione del ciclo lo < hi e aggiornamento hi = mid quando arr[mid] >= x. In questo modo il risultato converge alla prima posizione valida.
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)) # 4Implementare l'upper bound (bisect_right)
bisect_right(arr, x) restituisce il primo indice i tale che arr[i] > x. Rispetto a bisect_left cambia una sola riga: la condizione passa da arr[mid] < x a arr[mid] <= x. Quando arr[mid] <= x, la risposta si trova strettamente a destra di mid, quindi impostiamo lo = mid + 1; altrimenti restringiamo la ricerca da destra.
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)) # 5Contare le occorrenze con entrambi i bound
Per contare le occorrenze di un target in un array ordinato in O(log n), applichi entrambi i bound: count = bisect_right(arr, target) - bisect_left(arr, target). Se il conteggio è 0, il target è assente. Questo è significativamente più veloce di una scansione lineare ed è l'approccio standard per le query di frequenza su dati ordinati.
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)) # 1Trovare la prima e l'ultima posizione del target
LeetCode 34 'Find First and Last Position of Element in Sorted Array' chiede di restituire [first_idx, last_idx] in O(log n). La prima posizione è bisect_left(arr, target), ma solo se arr[result] == target. L'ultima posizione è bisect_right(arr, target) - 1. Se uno dei due controlli fallisce, restituisca [-1, -1].
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]Posizione di inserimento (LeetCode 35)
LeetCode 35 'Search Insert Position' chiede: dove verrebbe inserito il target per mantenere ordinato l'array? Questo corrisponde esattamente a bisect_left(arr, target). Se il target esiste, bisect_left restituisce il suo indice. Se non esiste, bisect_left restituisce l'indice in cui verrebbe inserito. Non sono necessari casi speciali: la stessa funzione gestisce entrambe le situazioni.
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)La differenza tra bisect_left e bisect_right
Quando non ci sono duplicati, bisect_left e bisect_right restituiscono lo stesso indice. La differenza conta solo quando il target compare più volte. bisect_left indica la prima copia; bisect_right indica la posizione immediatamente successiva all'ultima copia. La scelta dipende dal fatto che si desideri inserire prima delle copie esistenti, usando left, oppure dopo, usando right.
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)) # 4Applicare i bound alle query di frequenza su dati ordinati
Per rispondere in modo efficiente a molte query sulla frequenza degli elementi di un array ordinato, precalcoli l'array ordinato una sola volta e utilizzi bisect per ogni query. Ogni query determina quanti elementi si trovano in [lo, hi] in O(log n) anziché O(n). Questo schema compare nei problemi che richiedono di contare gli elementi all'interno di un intervallo di valori dopo l'ordinamento.
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)Ricerca binaria con chiave personalizzata
A volte la chiave di ricerca non è il valore memorizzato, ma una proprietà derivata. Il modulo bisect di Python non supporta direttamente una funzione key, ma è possibile eseguire manualmente una ricerca binaria applicando la chiave all'interno del ciclo. Questo schema compare quando si cerca in una lista di oggetti in base a uno dei loro attributi.
# 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')]Errori comuni nei colloqui con i bound
L'errore più comune è dimenticare di eseguire la validazione dopo aver chiamato bisect_left. La funzione restituisce sempre un indice di inserimento valido, ma non garantisce che l'elemento a quell'indice sia uguale al target. Controlli sempre arr[result] == target prima di presumere che il target sia stato trovato.
Un secondo errore consiste nell'usare bisect_right quando si desidera la prima occorrenza: bisect_right restituisce la posizione successiva all'ultima occorrenza, quindi sottraendo 1 si ottiene l'ultima, non la prima.
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) # FalseRiepilogo: quando usare bisect_left e bisect_right
Utilizzi bisect_left quando le serve la prima occorrenza del target, il punto di inserimento che sposta a destra le copie esistenti oppure la verifica dell'esistenza del target. Utilizzi bisect_right quando le serve la posizione successiva all'ultima occorrenza, il punto di inserimento dopo tutte le copie esistenti oppure il conteggio degli elementi <= target (che corrisponde a bisect_right(arr, target)).
Entrambe hanno complessità O(log n) e fanno parte della libreria standard di Python, quindi può importarle e utilizzarle direttamente, a meno che il selezionatore non le chieda di implementarle da zero.
Verifica rapida
Verifichi la comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: bisect_left trova il primo elemento >= target, bisect_right trova il primo elemento > target, cioè la posizione successiva all'ultima occorrenza e la loro differenza fornisce il conteggio delle occorrenze in O(log n). Nel prossimo argomento esploreremo la ricerca binaria nello spazio delle soluzioni, in cui lo spazio di ricerca è un intervallo di possibili risposte e non un indice di array.
Domande Frequenti
La lezione «Limite inferiore e limite superiore» è gratuita?
Sì — il testo completo di «Limite inferiore e limite superiore» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Limite inferiore e limite superiore»?
Implementi da zero bisect_left e bisect_right e li applichi per trovare la prima e l'ultima posizione di un valore obiettivo Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Limite inferiore e limite superiore»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Ricerca binaria classica: sinistra, destra, centro
- Ricerca binaria su array ruotati e non ordinati
- Limite inferiore e limite superiore
- Ricerca binaria nello spazio delle risposte