Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - [4]
Например:
Ищем компанию в телефонной книге с применением бинарного поиска
Рассмотрим пример того, как работает бинарный поиск. Сыграем в простую игру: я загадал число от 1 до 100.
Вы должны отгадать мое число, использовав как можно меньше попыток. При каждой попытке я буду давать один из трех ответов: «мало», «много» или «угадал».
Предположим, вы начинаете перебирать все варианты подряд: 1, 2, 3, 4 …. Вот как это будет выглядеть.
Плохой способ угадать число
Это пример простого поиска (возможно, термин «тупой поиск» был бы уместнее). При каждой догадке исключается только одно число. Если я загадал число 99, то, чтобы добраться до него, потребуется 99 попыток!
Более эффективный поиск
Существует другой, более эффективный способ. Начнем с 50.
Слишком мало… но вы только что исключили половину чисел! Теперь вы знаете, что все числа 1–50 меньше загаданного. Следующая попытка: 75.
На этот раз перелет… Но вы снова исключили половину оставшихся чисел! С бинарным поиском вы каждый раз загадываете число в середине диапазона и исключаете половину оставшихся чисел. Следующим будет число 63 (по середине между 50 и 75).
Так работает бинарный поиск. А вы только что узнали свой первый алгоритм! Попробуем поточнее определить, сколько чисел будет исключаться каждый раз.
При бинарном поиске каждый раз исключается половина чисел
Какое бы число я ни задумал, вы гарантированно сможете угадать его не более чем за 7 попыток, потому что с каждой попыткой исключается половина оставшихся чисел!
Предположим, вы ищете слово в словаре с 240 000 словами. Как вы думаете, сколько попыток вам понадобится в худшем случае?
При простом поиске может потребоваться 240 000 попыток, если искомое слово находится на самой последней позиции в книге. С каждым шагом бинарного поиска количество слов сокращается вдвое, пока не останется только одно слово.
Итак, бинарный поиск потребует 18 шагов — заметная разница! В общем случае для списка из n элементов бинарный поиск выполняется за log2n шагов, тогда как простой поиск будет выполнен за n шагов.
Логарифмы
Возможно, вы уже забыли, что такое логарифм, но наверняка помните, что такое возведение в степень. log10100 по сути означает, сколько раз нужно перемножить 10, чтобы получить 100. Правильный ответ — 2: 10 × 10. Итак, log10 100 = 2. Логарифм по смыслу противоположен возведению в степень.
Логарифм — операция, обратная возведению в степень
Когда я в этой книге упоминаю «O-большое» (об этом чуть позднее), log всегда означает log2. Когда вы ищете элемент с применением простого поиска, в худшем случае вам придется проверить каждый элемент. Итак, для списка из 8 чисел понадобится не больше 8 проверок. Для бинарного поиска в худшем случае потребуется не более logn проверок. Для списка из 8 элементов log 8 == 3, потому что 23 == 8. Итак, для списка из 8 чисел вам придется проверить не более 3 чисел. Для списка из 1024 элементов log 1024 = 10, потому что 210 == 1024. Следовательно, для списка из 1024 чисел придется проверить не более 10 чисел.
примечание
Бинарный поиск работает только в том случае, если список отсортирован. Например, имена в телефонной книге хранятся в алфавитном порядке, и вы можете воспользоваться бинарным поиском. А что произойдет, если имена не будут отсортированы?
Посмотрим, как написать реализацию бинарного поиска на Python. В следующем примере кода используется массив. Если вы не знаете, как работают массивы, не беспокойтесь: эта тема рассматривается в следующей главе. Пока достаточно знать, что серию элементов можно сохранить в непрерывной последовательности ячеек, которая называется массивом. Нумерация ячеек начинается с 0: первая ячейка находится в позиции с номером 0, вторая — в позиции с номером 1 и т.д.
Функция binary_search получает отсортированный массив и значение. Если значение присутствует в массиве, то функция возвращает его позицию. При этом мы должны следить за тем, в какой части массива проводится поиск. Вначале это весь массив:
low = 0
high = len(list) - 1
Каждый раз алгоритм проверяет средний элемент:
mid = (low + high) / 2 Если значение (low+high) нечетно, то Python автоматически округляет значение mid в меньшую сторону
guess = list[mid]
Если названное число было слишком мало, то переменная low обновляется соответственно:
if guess < item:
low = mid + 1
А если догадка была слишком велика, то обновляется переменная high. Полный код выглядит так:
def binary_search(list, item):
low = 0 В переменных low и high хранятся границы той части списка, в которой выполняется поиск
high = len(list)—1
while low <= high:
mid = (low + high)/2
guess = list[mid]
if guess == item:
return mid
if guess > item:
high = mid - 1
else:
low = mid + 1
return None
my_list = [1, 3, 5, 7, 9]
print binary_search(my_list, 3) # => 1
print binary_search(my_list, -1) # => None
