Метод двоичного поиска: каждый вопрос «больше или меньше N?» делит диапазон пополам. 1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1. За 10 вопросов можно угадать любое число до 1024 (2¹⁰). Именно так работают алгоритмы поиска в компьютерах.
Попроси друга загадать число от 1 до 1000. Ты задашь ровно 10 вопросов типа «да/нет» - и назовёшь число. Любое. Из тысячи вариантов.
Не веришь? Проверь.
Метод: бинарный поиск
Каждый вопрос делит оставшийся диапазон пополам. Вот как это работает.
Загадано число от 1 до 1000.
Вопрос 1: «Число больше 500?» Допустим, да. Остаётся 501–1000. Вопрос 2: «Больше 750?» Нет. Остаётся 501–750. Вопрос 3: «Больше 625?» Да. Остаётся 626–750. Вопрос 4: «Больше 688?» Нет. Остаётся 626–688. Вопрос 5: «Больше 657?» Да. Остаётся 658–688. Вопрос 6: «Больше 673?» Нет. Остаётся 658–673. Вопрос 7: «Больше 665?» Да. Остаётся 666–673. Вопрос 8: «Больше 669?» Нет. Остаётся 666–669. Вопрос 9: «Больше 667?» Да. Остаётся 668–669. Вопрос 10: «Это 669?» Да.
Десять вопросов. Из тысячи вариантов. Точное попадание.
Почему 10 вопросов хватает на 1000
Каждый вопрос уменьшает количество вариантов вдвое. После 10 вопросов остаётся: 1000 / 2¹⁰ = 1000 / 1024 ≈ 1. Один вариант.
Формула: количество вопросов = log₂(N). Для 1000: log₂(1000) ≈ 10.
Для миллиона чисел хватит 20 вопросов. Для миллиарда - 30. Логарифм растёт невероятно медленно - это «антиэкспонента». Если экспонента (зёрна на шахматной доске) растёт пугающе быстро, то логарифм - успокаивающе медленно.
Где это используется
Программисты называют это «бинарный поиск» - один из фундаментальных алгоритмов информатики. Когда ты ищешь слово в словаре - ты делаешь бинарный поиск интуитивно: открываешь посередине, смотришь - раньше или позже нужная буква, открываешь в нужной половине.
Google ищет среди миллиардов страниц за доли секунды - потому что использует принципы, выросшие из этого простого метода деления пополам.
А вы знали?
Бинарный поиск изобрели в 1946 году, но первую правильную реализацию без ошибок написали только в 1962-м. 16 лет программисты допускали ошибку в простейшем алгоритме. А в 2006 году обнаружили баг в реализации бинарного поиска в стандартной библиотеке Java - он существовал 9 лет. Простое не значит лёгкое.
Что далее
Почему пуля в воде теряет убойную силу через метр - факт, который спасал жизни и вдохновлял кинематографистов.
Покажете фокус друзьям? Пишите в комментариях!
Если вы дочитали до конца - вам точно сюда. Подпишитесь, чтобы не потерять канал! Каждый день - одна задача, один фокус или один факт, всегда есть повод удивиться.
Читайте также:
Канал «А вы знали?» - задачи, фокусы и наука. Каждый день - повод удивиться.