Грокаем алгоритмы

Существует другой, более эффективный способ. Начнем с 50.

Слишком мало ... но вы только что исключили половину чисел! Теперь вы знаете, что все числа 1-50 меньше загаданного. Следующая попытка: 75.

На этот раз перелет ... Но вы снова исключили половину оставшихся чисел! С бинарным поиском вы каждый раз загадываете число в середине диапазона и исключаете половину оставшихся чисел. Следующим будет число 63 (по середине между 50 и 75).

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

При бинарном поиске каждый раз исключается половина чисел

Какое бы число я ни задумал, вы гарантированно сможете угадать его не более чем за 7 попыток, потому что с каждой попыткой исключается половина оставшихся чисел!

Предположим, вы ищете слово в словаре с 240 ООО словами. Как вы думаете, сколько попыток вам понадобится в худшем случае?

При простом поиске может потребоваться 240 ООО попыток, если искомое слово находится на самой последней позиции в книге. С каждым шагом бинарного поиска количество слов сокращается вдвое , пока не останется только одно слово.

Итак, бинарный поиск потребует 18 шагов - заметная разница! В общем случае для списка из п элементов бинарный поиск выполняется за log2n шагов, тогда как простой поиск будет выполнен за n шагов.

ПРИМЕЧАНИЕ
Бинарный поиск работает только в том случае, если список отсортирован. Например, имена в телефонной книге хранятся в алфавитном порядке, и вы можете воспользоваться бинарным поиском. А что произойдет, если имена не будут отсортированы?

Посмотрим, как написать реализацию бинарного поиска на Python. В следующем примере кода используется массив. Если вы не знаете, как работают массивы, не беспокойтесь: эта тема рассматривается в следующей главе.Пока достаточно знать , что серию элементов можно сохранить в непрерывной последовательности ячеек, которая называется массивом. Нумерация ячеек начинается с О: первая ячейка находится в позиции с номером О,вторая - в позиции с номером 1 и т. д.

Функция binary_search получает отсортированный массив и значение. Если значение присутствует в массиве, то функция возвращает его позицию. При этом мы должны следить за тем, в какой части массива проводится поиск.Вначале это весь массив:

Каждый раз алгоритм проверяет средний элемент:

Если названное число было слишком мало, то переменная low обновляется
соответственно:

А если догадка была слишком велика, то обновляется переменная high. Полный
код выглядит так:

УПРАЖНЕНИЯ

1.1 Имеется отсортированный список из 128 имен, и вы ищете в нем значение
методом бинарного поиска. Какое максимальное количество
проверок для этого может потребоваться?

1.2 Предположим, размер списка увеличился вдвое. Как изменится максимальное
количество проверок?