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

На этот раз перелет… Но вы снова исключили половину оставшихся чисел! С бинарным поиском вы каждый раз загадываете число в середине диапазона и исключаете половину оставшихся чисел. Следующим будет число 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]