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)
- Θ(log n)
- caso peggiore O(log n)
- spazio O(1)
log₂ n: quante volte si può dimezzare n prima di arrivare a 1. Per 64 valori sono 6, quindi al massimo 7 confronti.
Altri termini in questa pagina
- 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.
- centro (mid)
- trovato
- scartato
- bersaglio
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.