Ricerca binaria — algoritmo, complessità temporale e codice

La ricerca binaria è un modo veloce per trovare un valore in una lista ordinata. Si controlla l’elemento centrale, si esclude metà dei valori rimanenti e si ripete. Se la lista non è ordinata, questa logica non vale.

In una lista in ordine crescente, la regola è semplice: se il valore centrale è minore del valore cercato, si cerca a destra; se è maggiore, si cerca a sinistra. Poiché l’intervallo si riduce ogni volta di circa la metà, la ricerca binaria ha complessità temporale $O(\log n)$.

Come funziona la ricerca binaria su una lista ordinata

Usa questa lista ordinata:

$$[3, 7, 12, 18, 24, 31, 39, 45, 52]$$

Supponiamo che il valore cercato sia $31$.

Si parte con l’intero intervallo. Il valore centrale è $24$. Poiché $31 > 24$, tutto ciò che si trova a sinistra di $24$ può essere scartato, quindi la ricerca continua in

$$[31, 39, 45, 52]$$

Ora il valore centrale è $39$. Poiché $31 < 39$, tutto ciò che si trova a destra di $39$ può essere scartato, quindi l’intervallo diventa

$$[31]$$

Ora il valore centrale è $31$, quindi la ricerca si ferma. L’idea utile non è solo che il valore cercato è stato trovato. In due confronti, l’intervallo dei candidati è passato da $9$ valori a $1$.

Perché la ricerca binaria è in $O(\log n)$

Ogni confronto elimina circa metà dei candidati rimanenti. Dopo un passo, restano circa $n/2$ elementi. Dopo due passi, ne restano circa $n/4$. Dopo $k$ passi, la dimensione rimanente è circa

$$\frac{n}{2^k}$$

La ricerca termina quando questa quantità è circa $1$, quindi il numero di passi soddisfa

$$2^k \approx n$$

Prendendo il $\log_2$ di entrambi i lati si ottiene

$$k \approx \log_2 n$$

Ecco perché la ricerca binaria scala bene. Una ricerca lineare può richiedere fino a $n$ controlli, ma la ricerca binaria richiede solo abbastanza controlli da continuare a dimezzare l’intervallo.

Esempio di codice per la ricerca binaria

Ecco una versione iterativa standard in Python: