Почему поиск в отсортированном списке — это деление пополам
Угадать число от 1 до миллиона можно всего за 20 вопросов — если задавать их с умом. Тот же фокус прячется внутри телефонной книги, словаря и любого быстрого поиска. Разбираемся, почему деление пополам бьёт перебор наповал.
Загадай число от 1 до миллиона, а я угадаю его, задав всего двадцать вопросов «больше или меньше?». Звучит как магия или жульничество, но это чистая математика. И ровно тот же приём заставляет компьютер находить нужную строчку среди миллиардов за доли секунды.
Игра в угадайку, в которую играет твой компьютер
Представь: я загадал число от 1 до 100. Ты можешь спрашивать, а я отвечаю только «больше» или «меньше». Как угадать побыстрее?
Можно тыкать подряд: «Это 1? Это 2? Это 3?» В худшем случае придётся задать сто вопросов. Скучно и долго. Но есть способ хитрее. Первый вопрос — «Это 50?» Если я говорю «больше», ты мгновенно вычёркиваешь всю нижнюю половину — числа от 1 до 50 больше не интересны. Осталось 50 вариантов. Следующий вопрос — про серединку оставшегося, скажем, 75. И снова половина отпадает.
Каждый вопрос выбрасывает ровно половину оставшихся вариантов. Это и есть бинарный поиск — «бинарный» значит «на два», потому что на каждом шаге мир делится надвое.
Почему обязательно нужен порядок
Весь фокус держится на одном условии: список должен быть отсортирован. Без порядка ответ «больше или меньше» бессмысленен.
Вспомни обычную бумажную телефонную книгу или словарь. Ты ведь не читаешь её с первой страницы, чтобы найти слово «черепаха». Ты раскрываешь книгу примерно посередине, смотришь на букву и думаешь: «Тут буква М, а мне нужна Ч — значит, листаю дальше, вправо». Открываешь середину правой части — там уже Т. Ещё ближе. Пара движений — и ты на нужной странице.
Сортировка — это плата вперёд. Один раз навёл порядок — и потом ищешь молниеносно сколько угодно раз.
А теперь представь словарь, в котором слова свалены в случайном порядке. Открыл середину — увидел «банан». И что это тебе говорит про то, где «черепаха»? Ровным счётом ничего. Придётся проверять каждое слово подряд. Именно поэтому деление пополам работает только там, где есть порядок: знание про серединку сразу рассказывает, в какой половине искать.
Двадцать вопросов на миллион
Теперь самое красивое. Давай посчитаем, сколько вопросов нужно на самом деле.
Каждый шаг режет список пополам. Значит, вопрос не в том, «сколько там элементов», а в том, сколько раз число можно поделить на два, пока не останется один.
- 100 элементов — около 7 шагов (100 → 50 → 25 → 13 → 7 → 4 → 2 → 1).
- 1000 элементов — всего 10 шагов.
- 1 000 000 элементов — около 20 шагов.
- 1 000 000 000 элементов — примерно 30 шагов.
Вдумайся: список вырос в тысячу раз — с миллиона до миллиарда, — а работы прибавилось всего на десяток вопросов. Это и есть знаменитый логарифм. Математики записывают такую скорость как O(log n), но за страшным значком прячется простая мысль: чтобы добавить один лишний шаг, размер задачи нужно удвоить.
Сравни с тупым перебором по очереди — там для миллиона элементов в худшем случае миллион проверок, а не двадцать. Разница между «мгновенно» и «можно успеть пообедать».
Складывание листа бумаги наоборот
Есть известный факт: обычный лист бумаги нельзя сложить пополам больше семи-восьми раз — он становится слишком толстым и упрямым. С каждым складыванием толщина удваивается, и она растёт пугающе быстро.
Бинарный поиск — это та же история, только прокрученная задом наперёд. Ты не складываешь, а раскладываешь задачу обратно: на каждом шаге кусок, в котором может прятаться ответ, делится надвое и худеет вдвое. То, что при складывании за считанные шаги раздувается до огромной толщины, при поиске за те же считанные шаги сжимается с миллиона до единицы.
Именно поэтому экспоненциальный рост, который кажется нам таким стремительным, в зеркале превращается в логарифм — невероятно медленный и оттого невероятно полезный.
Где это живёт на самом деле
Бинарный поиск — не школьная задачка ради задачки. Он работает прямо сейчас вокруг тебя:
- Базы данных. Когда ты пишешь в мессенджере и видишь подсказку контакта, под капотом по упорядоченному индексу бежит поиск делением пополам.
- git bisect. Программисты ищут, в каком из тысяч коммитов сломался код — проверяют середину истории, отбрасывают половину, и так до виновника.
- Угадай число. Та самая детская игра — буквально оптимальная стратегия и есть бинарный поиск.
Так что в следующий раз, когда захочешь кого-то впечатлить, предложи загадать число до миллиона и пообещай угадать за двадцать вопросов. Ты не экстрасенс. Ты просто умеешь делить пополам — и теперь знаешь, почему это работает.