Бинарный поиск простыми словами

Алгоритмом называется набор инструкций для выполнения некоторой задачи.

Бинарный поиск — это алгоритм, на входе он получает отсортированный список элементов.

Таким образом, если элемент, который вы ищете, присутствует в списке, то бинарный поиск возвращает ту позицию, в которой он был найден.

В противном случае бинарный поиск возвращает null.

Рассмотрим пример того, как работает бинарный поиск. Сыграем в простую игру: я загадал число от 1 до 100.

123….100

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

Предположм, вы начинаете перебирать все варианты подряд:1,2,3,4
Вот как это будет выглядеть.

Бинарный поиск

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

Бинарный поиск

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

Бинарный поиск

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

Бинарный поиск

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

Бинарный поиск

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

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

Простой поиск:____шагов
Бинарный поиск:____шагов

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

Бинарный поиск

Давайте напишем реализцию бинарного поиска на Python.

def binary_search(list, item): # В переменных low и high хранятся границы той части списка, в которой выполняется поиск low = 0 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

Упражнения:

  1. Имеется отсортированный список из 128 имен, и вы ищите в нем значение методом бинарного поиска. Какое максимальное количество проверок для этого может потребоваться?
  2. Предположим, размер списка увеличился вдвое (256 имен). Как изменится максимальное количество проверок?

Ответы:

  1. 7
  2. 8

Чтобы не пропускать новые выпуски подписывайтесь на канал  @world_hello_ru

Добавить комментарий

Ваш адрес email не будет опубликован.