Informatik · Binäre Suche
Wie findet man einen Namen unter einer Million in 20 Schritten?
Was du siehst
Ein Telefonbuch enthält eine Million Namen, alphabetisch geordnet. Sie einzeln zu prüfen, könnte eine Million Blicke kosten. Geht das besser? Schlag es genau in der Mitte auf. Der gesuchte Name kommt später, also fällt die ganze erste Hälfte weg. Eine halbe Million bleibt. Schlag die Mitte des Rests auf und halbiere wieder. Und wieder. Jeder Blick wirft die Hälfte des Rests weg. Zwanzig Halbierungen bringen eine Million auf eins, denn zwei hoch zwanzig ist knapp über eine Million. Eine Milliarde Namen? Nur zehn Blicke mehr.
