Ricerca binaria: come funziona e perché è facile sbagliarla

La ricerca binaria è uno degli algoritmi più semplici da descrivere e, sorprendentemente, uno dei più facili da implementare male. L'idea si spiega in una frase: in un elenco ordinato, guarda l'elemento centrale e scarta la metà in cui il valore cercato non può trovarsi. Eppure molte implementazioni scritte di getto contengono errori nei confini che emergono solo in casi particolari. Capirla a fondo è un ottimo esercizio di ragionamento rigoroso.

L'idea

Immagina di cercare il numero 37 in questo elenco ordinato:

3  8  12  19  25  31  37  42  50  61  74

Invece di scorrerlo dall'inizio, guardi l'elemento centrale: 31. Poiché 37 è maggiore, se esiste deve trovarsi nella metà destra. Ripeti sulla metà destra (37, 42, 50, 61, 74): il centrale è 50, troppo grande, quindi guardi a sinistra. Restano 37 e 42: trovato al passo successivo.

Ogni confronto dimezza lo spazio di ricerca. Per questo la complessità è O(log n): con un milione di elementi bastano una ventina di confronti, contro il milione che potrebbe servire con una ricerca lineare.

Il requisito fondamentale

La ricerca binaria funziona solo su dati ordinati, secondo lo stesso criterio usato per confrontare. Se l'elenco non è ordinato, l'algoritmo non segnala errori: restituisce semplicemente risultati sbagliati. Ordinare costa O(n log n), quindi conviene quando si fanno molte ricerche sugli stessi dati, oppure quando i dati sono già ordinati per natura, come un registro di eventi in ordine di tempo.

Un'implementazione corretta

def ricerca_binaria(elenco, valore):
    sinistra, destra = 0, len(elenco) - 1
    while sinistra <= destra:
        medio = (sinistra + destra) // 2
        if elenco[medio] == valore:
            return medio
        if elenco[medio] < valore:
            sinistra = medio + 1
        else:
            destra = medio - 1
    return -1

Ogni dettaglio conta:

1. destra parte da len(elenco) - 1, l'ultimo indice valido;
2. la condizione è <=, perché quando sinistra == destra resta ancora un elemento da controllare;
3. dopo il confronto si esclude medio con + 1 e - 1, altrimenti il ciclo può non terminare.

Gli errori classici

Esiste anche un errore storico legato al calcolo del punto medio: in linguaggi con interi di dimensione fissa, come Java o C, la somma sinistra + destra può superare il valore massimo rappresentabile con array molto grandi. La forma sinistra + (destra - sinistra) / 2 evita il problema. In Python gli interi non hanno limite di dimensione, quindi la questione non si pone, ma è utile conoscerla.

La regola pratica per evitare questi errori: scegli una convenzione sui confini e mantienila. O entrambi inclusivi, come nell'esempio, oppure sinistro inclusivo e destro esclusivo, ma mai un misto.

Usa la libreria quando puoi

Python offre il modulo bisect, che implementa la ricerca binaria in modo corretto e veloce:

from bisect import bisect_left

def indice_di(elenco, valore):
    i = bisect_left(elenco, valore)
    if i < len(elenco) and elenco[i] == valore:
        return i
    return -1

bisect_left restituisce la posizione in cui il valore andrebbe inserito per mantenere l'ordine. Questo lo rende utile anche per inserire elementi in un elenco ordinato o per contare quanti valori sono minori di una soglia.

Oltre la ricerca di un valore

La forza della ricerca binaria è che si applica a qualunque problema in cui una condizione è falsa fino a un certo punto e vera da lì in poi. Alcuni esempi concreti:

• trovare il primo giorno in cui un indicatore supera una soglia in una serie temporale ordinata;
• trovare una versione difettosa: è esattamente ciò che fa git bisect sulla storia dei commit;
• trovare un valore ottimale: per esempio la dimensione minima di un buffer che fa passare un test, provando valori sempre più vicini;
• cercare in intervalli: assegnare un punteggio a una fascia («fino a 18: insufficiente, fino a 24: sufficiente...») cercando la soglia giusta in un elenco di limiti.

In tutti questi casi non si cerca un elemento uguale, ma il punto di confine. Pensare alla ricerca binaria in questi termini la trasforma da esercizio scolastico a strumento di uso quotidiano.

Come verificarla

Una ricerca binaria va testata proprio dove sbaglia più spesso: elenco vuoto, elenco di un solo elemento, valore al primo e all'ultimo posto, valore assente minore di tutti o maggiore di tutti, elementi duplicati. Un test efficace confronta i risultati con una semplice ricerca lineare su molti elenchi generati: se i due metodi non concordano, c'è un errore.

In sintesi

• La ricerca binaria dimezza lo spazio di ricerca a ogni passo e ha complessità O(log n).
• Funziona solo su dati ordinati: altrimenti restituisce risultati sbagliati senza avvisare.
• Gli errori tipici riguardano i confini: scegli una convenzione e rispettala.
• In Python usa il modulo bisect invece di riscriverla da zero.
• Si applica a qualunque problema con un punto di confine, non solo alla ricerca di un valore.