Ricerca binaria: dimezzare la ricerca — Informatica, 7–10
Quando una lista è già ordinata, non devi controllare ogni elemento uno alla volta. La ricerca binaria guarda il centro, decide in quale metà può trovarsi la risposta e ripete il procedimento finché la trova o stabilisce che non c'è.
Dimezzare sempre le possibilità
Immagina che un numero segreto sia nascosto in una fila ordinata. Invece di partire dal primo, guarda quello al centro. Se il bersaglio è maggiore, scarta la metà più bassa; se è minore, scarta quella più alta. Ogni risposta elimina circa metà delle possibilità, così la ricerca si riduce velocemente.
Perché non controllare ogni elemento?
Partire dall'inizio va bene per una lista corta, ma diventa lento con migliaia o milioni di elementi ordinati. La ricerca binaria usa l'ordine come indizio invece di sprecarlo. Nasce da una domanda sensata: come possiamo eliminare più posti sbagliati possibile con un solo controllo?
Trovare 73 in una lista
La lista ordinata è 12, 25, 31, 44, 58, 73, 81, 90. Prima controlla il centro: 44. Poiché 73 è maggiore, tieni 58, 73, 81, 90. Controlla il centro di questi numeri: 73. Trovi il bersaglio con due controlli, invece di esaminare tutti gli otto numeri dall'inizio.
L'ordine è indispensabile
È ragionevole guardare il centro di qualsiasi lista, perché il centro sembra una buona scorciatoia. Ma nella lista 12, 90, 25, 73, 44, 81, 31, 58, vedere 44 non dice in quale metà si trova 73. La ricerca binaria funziona solo se la lista è ordinata secondo ciò che stai confrontando.
Trovare le cose velocemente
Un dizionario usa l'ordine alfabetico, quindi puoi aprirlo vicino al centro e restringere la ricerca di una parola. I programmi usano la stessa strategia con nomi, numeri e registri ordinati. È utile quando la lista è grande e già ordinata; ordinarla prima può richiedere lavoro extra, quindi la scorciatoia non è sempre la scelta migliore.
Continua a esplorare
Altre lingue
Caricamento di MyLeoNes™…