Грокаем а Иллюстрированное пособие для программистов и любопытствующих

Ищем компанию в телефонной книге с применением бинарного поиска


апример:
Р
ассмотрим пример того, как работает бинарный поиск. Сыграем в простую игру: я загадал число от 1 до 100.
Вы должны отгадать мое число, использовав как можно меньше попыток. При каждой попытке я буду давать один из трех ответов: «мало», «много» или «угадал».
П


Д- I 3 1 ||W>1

редположим, вы начинаете перебирать все варианты подряд: 1, 2, 3, 4 .... Вот как это будет выглядеть.
П
лохой способ угадать число
Это пример простого поиска (возможно, термин «тупой поиск» был бы уместнее). При каждой догадке исключается только одно число. Если я за­гадал число 99, то, чтобы добраться до него, потребуется 99 попыток!
Более эффективный поиск
С

ЬСЕ ЭТИ ЧИСЛА СЛИШКОМ МАЛЫ1

уществует другой, более эффективный способ. Начнем с 50.
С
лишком мало... но вы только что исключили половину чисел! Теперь вы знаете, что все числа 1-50 меньше загаданного. Следующая попытка: 75.
Н
а этот раз перелет... Но вы снова исключили половину оставшихся чисел! С бинарнъш поиском вы каждый раз загадываете число в середине диапазона и исключаете половину оставшихся чисел. Следующим будет число 63 (по середине между 50 и 75).
Т
100 ЭЛЕМЕНТОВ


50


2S


'(Щ ^Ц(-и]-, щ

ак работает бинарный поиск. А вы только что узнали свой первый алго­ритм! Попробуем поточнее определить, сколько чисел будет исключаться каждый раз.
? ШАГОВ