Ricerca binaria

La ricerca binaria è il modo in cui cerchi una parola nel dizionario: lo apri a metà, guardi se la parola viene prima o dopo, e ripeti con quella metà. In una lista ordinata trova qualsiasi valore tra un milione in al massimo 20 confronti.

Una fila ordinata di barre con la barra centrale evidenziata, metà della fila sbiadita e una linea tratteggiata all'altezza dell'obiettivo
Una fila ordinata di barre con la barra centrale evidenziata, metà della fila sbiadita e una linea tratteggiata all'altezza dell'obiettivo

L'idea

In una lista ordinata, un confronto ti dice più che se hai trovato l'obiettivo: ti dice da che parte si trova. Confronta l'obiettivo con il valore al centro. Se sono uguali, hai finito. Se il valore centrale è più piccolo, anche tutto ciò che lo precede è più piccolo, quindi l'obiettivo può stare solo dopo. Se è più grande, l'obiettivo può stare solo prima. Tieni solo quella metà e ripeti.

Un esempio

Cerca 23 in 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Il valore centrale è 16, più piccolo, quindi restano solo i valori da 23 a 91. Il loro centro è 56, più grande, quindi restano solo 23 e 38. Il loro centro è 23: trovato in posizione 6 dopo 3 confronti, mentre la ricerca lineare ne richiede 6. Cercare 40 nella stessa lista confronta 16, 56, 23 e 38, dopo di che non resta nulla: 4 confronti per sapere che 40 manca, contro 10 della ricerca lineare.

Dimezzando si fa presto

Dopo un confronto resta al massimo metà della lista, dopo due un quarto, dopo k al massimo circa n/2ᵏ. La ricerca si ferma quando non resta nulla, quindi richiede al massimo ⌊log₂ n⌋ + 1 confronti: 6 per 40 valori, 10 per 1.000, 20 per un milione e 30 per un miliardo. Raddoppiare la lista aggiunge un solo confronto. Si scrive O(log n).

Facile da descrivere, difficile da scrivere bene

John Mauchly descrisse la ricerca binaria nel 1946, ma secondo Donald Knuth la prima versione che funzionava per ogni lunghezza della lista fu pubblicata solo nel 1962. Jon Bentley scoprì poi che solo un programmatore professionista su dieci circa la scriveva correttamente: le condizioni di arresto e il più o meno uno quando si dividono le metà sono facili da sbagliare. Nel 2006 Joshua Bloch mostrò che il modo comune di trovare il centro, (low + high) / 2, può andare in overflow con liste molto lunghe, un bug rimasto per anni nella libreria Java. Scrivere low + (high − low) / 2, come fa l'app, lo evita.

John Mauchly (quinto da sinistra) con altri responsabili dell’ENIAC davanti alla macchina, in una fotografia dell’esercito statunitense. Mauchly descrisse la ricerca binaria nel 1946.
John Mauchly (quinto da sinistra) con altri responsabili dell’ENIAC davanti alla macchina, in una fotografia dell’esercito statunitense. Mauchly descrisse la ricerca binaria nel 1946.

Varianti e usi

Con i duplicati, la ricerca binaria trova una delle corrispondenze; le versioni che proseguono a sinistra o a destra trovano la prima o l'ultima, oppure la posizione in cui andrebbe inserito un valore mancante. La stessa idea del dimezzamento trova la radice di un'equazione (bisezione), la versione in cui è comparso un bug (git bisect) e la risposta a molti problemi di ottimizzazione. Gli alberi binari di ricerca memorizzano i dati in modo che ogni ricerca segua lo stesso percorso di dimezzamenti.

Provala

Apri l'app, scegli un valore in Cerca e premi Passo. La parte ombreggiata è dove l'obiettivo può ancora trovarsi; il valore centrale è evidenziato, e la metà esclusa sbiadisce. I riquadri mostrano quanti valori sono ancora possibili e quanti confronti servirebbero a una ricerca lineare per lo stesso valore. Cerca un valore mancante, oppure usa 40 barre, per vedere crescere il divario.

Domande frequenti

Qual è la complessità temporale della ricerca binaria?

O(log n): al massimo ⌊log₂ n⌋ + 1 confronti per n valori. Nel caso migliore basta un confronto, quando l'obiettivo è al centro. La versione iterativa richiede O(1) memoria aggiuntiva.

Che differenza c'è tra ricerca binaria e ricerca lineare?

La ricerca lineare controlla ogni valore a turno e funziona su qualsiasi lista, ma può richiedere n confronti. La ricerca binaria funziona solo su una lista ordinata, ma esclude metà di ciò che resta a ogni confronto, quindi ne richiede circa log₂ n.

Conviene ordinare una lista solo per usare la ricerca binaria?

Solo se ci cerchi molte volte. Ordinare richiede circa n log n passi, più di una singola ricerca lineare. Una volta ordinata la lista, ogni ricerca successiva costa pochissimo.

La ricerca binaria funziona anche su cose diverse dalle liste?

Sì, su qualsiasi cosa in cui un test ti dica da che parte della risposta sei: un intervallo di numeri, le versioni di un programma o i tentativi in un gioco del più o meno.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Prova la ricerca binaria