Компьютер угадывает число, которое вы загадали
Загадайте число в выбранном диапазоне и держите в голове. Компьютер будет называть число, а вы честно отвечаете: ваше загаданное больше, меньше или это оно.
Фокус с карточками: угадываю число от 1 до 63
Загадайте любое число от 1 до 63. Посмотрите на 6 карточек и отметьте те, где ваше число есть. Компьютер сразу назовёт загаданное — а внизу объяснит, почему это работает.
Главный эксперимент: сколько вопросов на самом деле?
Компьютер сам загадывает случайные числа много раз и считает, сколько вопросов нужно двум «игрокам»: тому, кто перебирает числа подряд (1, 2, 3, …), и тому, кто каждый раз делит диапазон пополам. Это и есть проверка нашей гипотезы.
Почему деление пополам такое быстрое
Представьте 1000 чисел в ряд. Вы называете среднее — 500. Вам отвечают «меньше». И сразу, одним вопросом, вы выбросили половину — числа от 500 до 1000 больше не нужны. Осталось 500. Называете 250 — снова выбрасываете половину. Осталось 250, потом 125, 63, 32, 16, 8, 4, 2, 1.
Каждый вопрос уменьшает «подозреваемых» вдвое. Поэтому важен не сам размер диапазона, а сколько раз его можно разделить пополам, пока не останется одно число. Это действие в математике называется логарифм по основанию 2 и обозначается log₂N.
Диапазон вырос в 100 000 раз (с 10 до миллиона), а вопросов стало больше всего в 5 раз. Вот почему поиск «пополам» используют везде: так работает поиск слова в словаре, так компьютер ищет файл среди миллионов и находит имя в телефонной книге.