Ricerca binaria classica: sinistra, destra, centro
Implementi la ricerca binaria iterativamente e ricorsivamente, gestisca con precisione i dettagli off-by-one dei limiti lo/hi e verifichi la correttezza con input limite
Ricerca binaria classica: sinistra, destra, centro è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 1 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 DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
Perché la ricerca binaria è importante
La ricerca binaria riduce una scansione lineare O(n) a O(log n), dimezzando lo spazio di ricerca a ogni passaggio. In un array di un milione di elementi, una scansione lineare richiede fino a 1.000.000 di confronti, mentre la ricerca binaria ne richiede al massimo 20. Questa efficienza la rende uno degli algoritmi più frequentemente verificati nei colloqui di programmazione.
L'idea fondamentale è che un array ordinato consente di decidere, dopo un solo confronto, quale metà dei dati rimanenti scartare completamente.
Il modello sinistra, centro, destra
La ricerca binaria utilizza tre puntatori agli indici: lo (limite sinistro), hi (limite destro) e mid (punto centrale). A ogni iterazione calcoli mid = (lo + hi) // 2 e confronti il target con arr[mid]. Se il target è minore, sposti hi = mid - 1; se è maggiore, sposti lo = mid + 1; se è uguale, lo hai trovato.
Il ciclo continua finché lo <= hi. Quando il ciclo termina senza trovare il target, restituisci -1.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9, 11], 7)) # 3
print(binary_search([1, 3, 5, 7, 9, 11], 6)) # -1Evitare l'overflow degli interi in mid
L'espressione mid = (lo + hi) // 2 può causare un overflow degli interi nei linguaggi che utilizzano interi a larghezza fissa (Java, C++). Gli interi di Python hanno precisione arbitraria, quindi l'overflow non si verifica mai; tuttavia, nei colloqui ci si aspetta comunque che conosca l'alternativa sicura: mid = lo + (hi - lo) // 2.
Questa forma calcola lo stesso punto centrale, ma aggiunge a lo solo metà della distanza invece di sommare prima entrambi i puntatori. Menzionarla durante un colloquio dimostra consapevolezza degli aspetti di basso livello.
# Safe mid calculation (important in Java/C++, good habit in Python too)
lo, hi = 0, 1_000_000_000
mid_unsafe = (lo + hi) // 2 # fine in Python
mid_safe = lo + (hi - lo) // 2 # same result, no overflow risk
print(mid_unsafe == mid_safe) # TrueLimiti inclusivi ed esclusivi
Uno degli aspetti più complessi della ricerca binaria consiste nello scegliere se hi debba indicare l'ultimo indice valido (inclusivo, hi = len(arr) - 1) oppure l'indice appena oltre la fine (esclusivo, hi = len(arr)). Convenzioni diverse richiedono condizioni del ciclo e aggiornamenti dei limiti differenti.
Con limiti inclusivi utilizzi while lo <= hi e aggiorni hi = mid - 1. Con limiti esclusivi utilizzi while lo < hi e aggiorni hi = mid. Confondere le due convenzioni è la causa più comune di errori nelle implementazioni della ricerca binaria.
# Exclusive hi variant — useful for bisect-style lower-bound
def search_exclusive(arr, target):
lo, hi = 0, len(arr) # hi is one past last
while lo < hi: # strictly less than
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid # NOT mid - 1
return lo if lo < len(arr) and arr[lo] == target else -1
print(search_exclusive([2, 4, 6, 8, 10], 6)) # 2Ricerca binaria ricorsiva
La ricerca binaria può essere scritta in modo ricorsivo, passando i limiti aggiornati lo e hi attraverso lo stack delle chiamate. Ogni chiamata ricorsiva dimezza lo spazio di ricerca, quindi la profondità è O(log n). Il caso base si verifica quando lo > hi (elemento non trovato) oppure quando arr[mid] == target (elemento trovato).
La versione iterativa è preferibile nel codice di produzione perché evita il costo aggiuntivo dei frame dello stack, ma quella ricorsiva comunica più chiaramente la struttura divide et impera su una lavagna.
def binary_search_rec(arr, target, lo, hi):
if lo > hi:
return -1
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_rec(arr, target, mid + 1, hi)
else:
return binary_search_rec(arr, target, lo, mid - 1)
arr = [1, 3, 5, 7, 9, 11]
print(binary_search_rec(arr, 9, 0, len(arr) - 1)) # 4Casi limite: array vuoto, elemento singolo
Una ricerca binaria robusta deve gestire i casi limite senza andare in errore. I tre più comuni sono: un array vuoto (il ciclo non viene mai eseguito e viene restituito correttamente -1), un array con un solo elemento (mid, lo e hi coincidono, quindi basta un confronto) e target esterni all'intervallo (lo alla fine supera hi e viene restituito -1).
Verifichi sempre l'implementazione con questi input prima di passare alle domande successive durante un colloquio.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print(binary_search([], 5)) # -1 (empty)
print(binary_search([7], 7)) # 0 (single, found)
print(binary_search([7], 3)) # -1 (single, not found)
print(binary_search([1,3,5], 0)) # -1 (below range)
print(binary_search([1,3,5], 9)) # -1 (above range)Complessità temporale e spaziale
La ricerca binaria ha una complessità temporale O(log n) perché ogni confronto dimezza lo spazio di ricerca. Dopo k confronti, lo spazio rimanente è n/2^k; la ricerca termina quando questo valore raggiunge 1, quindi k = log₂ n.
La complessità spaziale è O(1) per la versione iterativa (solo tre variabili intere) e O(log n) per la versione ricorsiva, a causa della profondità dello stack delle chiamate. Durante un colloquio indichi sempre entrambe e preferisca la forma iterativa quando lo spazio è limitato.
import math
for n in [10, 100, 1000, 1_000_000, 1_000_000_000]:
steps = math.ceil(math.log2(n + 1))
print(f'n={n:>12,} max comparisons={steps}')Ricerca di una corrispondenza esatta o di un limite
La ricerca binaria classica restituisce un indice qualsiasi in cui è presente il target. Tuttavia, molti problemi da colloquio chiedono la prima o l'ultima occorrenza di un target. In questi casi deve continuare la ricerca anche dopo aver trovato una corrispondenza: invece di restituire immediatamente il risultato, restringa il limite e continui.
Quando cerca la prima occorrenza, dopo aver trovato arr[mid] == target, registri mid come candidato e imposti hi = mid - 1. Per l'ultima occorrenza imposti lo = mid + 1.
def first_occurrence(arr, target):
lo, hi, result = 0, len(arr) - 1, -1
while lo <= hi:
mid = lo + (hi - lo) // 2
if arr[mid] == target:
result = mid
hi = mid - 1 # keep searching left
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return result
print(first_occurrence([1, 2, 2, 2, 3], 2)) # 1Utilizzo del modulo bisect di Python
La libreria standard di Python fornisce bisect.bisect_left(arr, x) e bisect.bisect_right(arr, x) per una ricerca binaria pronta per l'uso in produzione. bisect_left restituisce l'indice più a sinistra in cui è possibile inserire x mantenendo l'array ordinato, trovando di fatto la prima posizione in cui arr[i] >= x.
Durante un colloquio potrebbe esserle consentito utilizzare bisect; lo verifichi sempre prima. È comunque essenziale sapere come funziona internamente: si tratta di una ricerca binaria O(log n).
import bisect
arr = [1, 2, 2, 2, 3, 5]
print(bisect.bisect_left(arr, 2)) # 1 (first 2)
print(bisect.bisect_right(arr, 2)) # 4 (after last 2)
# Check if target exists
target = 3
idx = bisect.bisect_left(arr, target)
print(idx < len(arr) and arr[idx] == target) # TrueErrori comuni nella ricerca binaria
Tre errori causano la maggior parte dei problemi con la ricerca binaria durante i colloqui. Primo, condizione errata del ciclo: utilizzare < invece di <= con limiti inclusivi fa saltare l'ultimo elemento rimasto. Secondo, aggiornamento errato dei limiti: dimenticare +1 o -1 crea un ciclo infinito quando lo == hi. Terzo, operare su un array non ordinato: la ricerca binaria è corretta solo su dati ordinati.
Prima di scrivere una ricerca binaria, dichiari ad alta voce: 'L'array è ordinato, i miei limiti sono inclusivi e il ciclo viene eseguito finché lo <= hi.'
# BUG: infinite loop when lo == hi because hi = mid never moves past lo
def buggy(arr, target):
lo, hi = 0, len(arr) - 1
while lo < hi: # should be lo <= hi for exact-match
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid # stops, but never returns mid when found
return lo if arr[lo] == target else -1
print(buggy([1, 3, 5, 7], 7)) # 3 (works here by luck)
print(buggy([1, 3, 5, 7], 1)) # 0 (correct)
print(buggy([1, 3, 5, 7], 4)) # -1 (correct)Consigli per i colloqui sulla ricerca binaria
Quando vede un problema che riguarda un array ordinato, una funzione monotonicamente crescente o uno spazio di ricerca che può essere dimezzato, consideri immediatamente la ricerca binaria. Durante un colloquio, esponga il ragionamento: 'Poiché l'array è ordinato, posso scartare metà degli elementi a ogni confronto, ottenendo O(log n).'
Verifichi sempre la soluzione con almeno tre input: un valore all'inizio, un valore alla fine e un valore assente. Dichiarare spontaneamente la complessità, ad esempio 'tempo O(log n), spazio O(1)', prima che le venga chiesto dimostra solide basi.
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: la ricerca binaria dimezza lo spazio di ricerca a ogni passaggio, con un tempo O(log n); la convenzione con limiti inclusivi utilizza lo <= hi, con gli aggiornamenti lo = mid+1 e hi = mid-1; infine, per trovare la prima o l'ultima occorrenza si continua la ricerca dopo una corrispondenza, invece di restituire immediatamente il risultato. Nella prossima lezione vedremo come estendere la ricerca binaria agli array ruotati e non ordinati.
Domande Frequenti
La lezione «Ricerca binaria classica: sinistra, destra, centro» è gratuita?
Sì — il testo completo di «Ricerca binaria classica: sinistra, destra, centro» è 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 DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Ricerca binaria classica: sinistra, destra, centro»?
Implementi la ricerca binaria iterativamente e ricorsivamente, gestisca con precisione i dettagli off-by-one dei limiti lo/hi e verifichi la correttezza con input limite Eserciti DSA 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 DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA 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 1 di 4.
Quanto tempo richiede la lezione «Ricerca binaria classica: sinistra, destra, centro»?
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 DSA Interview Prep?
Sì. Ogni lezione DSA 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