Informatyka · Wyszukiwanie binarne
Jak znaleźć jedno nazwisko wśród miliona w 20 krokach?
Co zobaczysz
Książka telefoniczna zawiera milion nazwisk, w kolejności alfabetycznej. Sprawdzanie ich po kolei może wymagać miliona spojrzeń. Da się lepiej? Otwórz ją dokładnie w połowie. Szukane nazwisko jest dalej, więc cała pierwsza połowa odpada. Zostaje pół miliona. Otwórz środek tego, co zostało, i znowu podziel na pół. I jeszcze raz. Każde spojrzenie odrzuca połowę tego, co zostało. Dwadzieścia podziałów na pół sprowadza milion do jednego, bo dwa do potęgi dwudziestej to trochę ponad milion. Miliard nazwisk? Tylko dziesięć spojrzeń więcej.
