1 ГЛАВА 'Более эффективный поиск'
Существует другой, более эффективный способ. Начнем с 50.
Слишком мало ... но вы только что исключили половину чисел! Теперь вы знаете, что все числа 1-50 меньше загаданного. Следующая попытка: 75.
На этот раз перелет ... Но вы снова исключили половину оставшихся чисел! С бинарным поиском вы каждый раз загадываете число в середине диапазона и исключаете половину оставшихся чисел. Следующим будет число 63 (по середине между 50 и 75).
Так работает бинарный поиск. А вы только что узнали свой первый алгоритм! Попробуем поточнее определить, сколько чисел будет исключаться каждый раз.
При бинарном поиске каждый раз исключается половина чисел
Какое бы число я ни задумал, вы гарантированно сможете угадать его не более чем за 7 попыток, потому что с каждой попыткой исключается половина оставшихся чисел!
Предположим, вы ищете слово в словаре с 240 ООО словами. Как вы думаете, сколько попыток вам понадобится в худшем случае?
При простом поиске может потребоваться 240 ООО попыток, если искомое слово находится на самой последней позиции в книге. С каждым шагом бинарного поиска количество слов сокращается вдвое , пока не останется только одно слово.
Итак, бинарный поиск потребует 18 шагов - заметная разница! В общем случае для списка из п элементов бинарный поиск выполняется за log2n шагов, тогда как простой поиск будет выполнен за n шагов.
ПРИМЕЧАНИЕ
Бинарный поиск работает только в том случае, если список отсортирован. Например, имена в телефонной книге хранятся в алфавитном порядке, и вы можете воспользоваться бинарным поиском. А что произойдет, если имена не будут отсортированы?
Посмотрим, как написать реализацию бинарного поиска на Python. В следующем примере кода используется массив. Если вы не знаете, как работают массивы, не беспокойтесь: эта тема рассматривается в следующей главе.Пока достаточно знать , что серию элементов можно сохранить в непрерывной последовательности ячеек, которая называется массивом. Нумерация ячеек начинается с О: первая ячейка находится в позиции с номером О,вторая - в позиции с номером 1 и т. д.
Функция binary_search получает отсортированный массив и значение. Если значение присутствует в массиве, то функция возвращает его позицию. При этом мы должны следить за тем, в какой части массива проводится поиск.Вначале это весь массив:
Каждый раз алгоритм проверяет средний элемент:
Если названное число было слишком мало, то переменная low обновляется
соответственно:
А если догадка была слишком велика, то обновляется переменная high. Полный
код выглядит так:
УПРАЖНЕНИЯ
1.1 Имеется отсортированный список из 128 имен, и вы ищете в нем значение
методом бинарного поиска. Какое максимальное количество
проверок для этого может потребоваться?
1.2 Предположим, размер списка увеличился вдвое. Как изменится максимальное
количество проверок?