Informatica · La ricerca binaria
Come trovare un nome tra un milione in 20 passi?
Cosa vedrai
Un elenco telefonico contiene un milione di nomi, in ordine alfabetico. Controllarli uno per uno potrebbe richiedere un milione di occhiate. Si può fare meglio? Aprilo proprio a metà. Il nome che cerchi viene dopo, quindi tutta la prima metà sparisce. Ne resta mezzo milione. Apri a metà quel che resta, e dimezza di nuovo. E ancora. Ogni occhiata scarta metà di ciò che resta. Venti dimezzamenti portano un milione a uno, perché due alla ventesima è poco più di un milione. Un miliardo di nomi? Solo dieci occhiate in più.
