Информатика · Двоичный поиск
Как найти одно имя из миллиона за 20 шагов?
Что вы увидите
В телефонном справочнике миллион имён, по алфавиту. Проверка по одному может занять миллион взглядов. Можно ли быстрее? Откройте его ровно посередине. Нужное имя идёт дальше, значит вся первая половина отпадает. Осталось полмиллиона. Откройте середину того, что осталось, и снова разделите пополам. И ещё раз. Каждый взгляд отбрасывает половину оставшегося. Двадцать делений пополам сводят миллион к одному, потому что два в двадцатой степени чуть больше миллиона. Миллиард имён? Всего на десять взглядов больше.
