Informatica · Binair zoeken
Hoe vind je één naam tussen een miljoen in 20 stappen?
Wat je ziet
Een telefoonboek bevat een miljoen namen, op alfabetische volgorde. Ze één voor één nalopen kan een miljoen keer kijken kosten. Kan het beter? Sla het precies in het midden open. De naam die je zoekt komt later, dus de hele eerste helft valt af. Er blijft een half miljoen over. Sla het midden van de rest open, en halveer opnieuw. En nog eens. Elke blik gooit de helft van de rest weg. Twintig keer halveren brengt een miljoen terug tot één, want twee tot de twintigste is net iets meer dan een miljoen. Een miljard namen? Maar tien keer extra kijken.
