Ricerca binaria
Trova un valore in un array ordinato guardando al centro e scartando la metà in cui non può trovarsi. Ogni confronto dimezza quel che resta.
- caso migliore Ω(1)
- caso medio Θ(log n)
- caso peggiore O(log n)
- spazio O(1)
Cosa significano questi termini?
- Ordinato: in ordine crescente. La ricerca binaria ne ha bisogno; su dati non ordinati dà risposte sbagliate.
- Dimezzare: ogni confronto scarta metà di ciò che resta, la metà in cui il bersaglio non può stare.
- log₂ n: quante volte si può dimezzare n prima di arrivare a 1. Per 64 valori sono 6, quindi al massimo 7 confronti.
- centro (mid)
- trovato
- scartato
- bersaglio
Ogni centro che la ricerca potrebbe scegliere; un’esecuzione è un percorso verso il basso. Livelli: 5 = ⌈log₂(24 + 1)⌉, il massimo di confronti che può servire.
Cerco 70 tra 24 valori ordinati: tutto l’array è ancora in gioco.
Spazio: riproduci o metti in pausa. Frecce sinistra e destra: passo passo. Home e Fine: salta.
Prova così: Scegli un bersaglio che non è nell’array. La ricerca si ferma comunque dopo al massimo ⌈log₂(n + 1)⌉ confronti, quando lo supera hi.
Come funziona
La ricerca binaria tiene due segnaposto, lo e hi, attorno alla parte dell’array in cui il bersaglio può ancora essere. Guarda il valore al centro: se è il bersaglio ha finito; se è minore, il bersaglio può essere solo a destra, quindi lo passa oltre il centro; se è maggiore, hi passa prima. Ogni passo dimezza il resto: 64 valori richiedono al massimo 7 confronti, un milione al massimo 20. Quando lo supera hi non resta nulla: il valore non è nell’array.
Quando conviene usarlo
Usa la ricerca binaria ogni volta che i dati sono ordinati e puoi saltare a qualsiasi posizione: una parola in un elenco ordinato, una versione in una cronologia di rilasci, git bisect, il punto in cui inserire in un array ordinato. Su dati non ordinati dà risposte sbagliate, e ordinare prima conviene solo se cerchi molte volte.