Играем в «Угадай число». Как поможет бинарный поиск
Хотите сыграть в простую игру? Предположим, я загадал число от 0 до 100. Отгадайте какое число я загадал, использовав как можно меньше попыток. При каждой попытке вы будете получать один из ответов: «мало», «много», «угадал».
Угадываем число через простой поиск
Возможно, вы начнёте перебирать все варианты подряд: 1, 2, 3, 4 ... и т.д
При каждым ответе будет исключаться только одно число. Это пример работы простого поиска. Рано или поздно мы дойдём до правильного ответа. Но представьте, если бы я загадал число 99. Чтобы до него добраться, потребуется 99 попыток. Долго.
Более эффективный способ
Мало. Но мы только что исключили половину чисел! Теперь мы знаем, что все числа 1 — 50 меньше загаданного. Делаем следующую попытку.
Много, но мы снова исключили половину чисел! Начинаем использовать бинарный поиск.
С бинарным поиском мы каждый раз загадываем число в середине диапазона и исключаем половину оставшихся чисел.
Называем следующее число. Это будет 63 (середина между 50 и 75).
Бинарный поиск работает только в том случае, если список отсортирован. Например, бумажный телефонный справочник. Имена абонентов в нём хранятся в алфавитном порядке и при поиске нужного номера телефона можно воспользоваться бинарным поиском.
Что почитать по теме: «Грокаем алгоритмы» Адитья Бхаргава