Алгоритмом называется набор инструкций для выполнения некоторой задачи.
Бинарный поиск — это алгоритм, на входе он получает отсортированный список элементов.
Таким образом, если элемент, который вы ищете, присутствует в списке, то бинарный поиск возвращает ту позицию, в которой он был найден.
В противном случае бинарный поиск возвращает null.
Рассмотрим пример того, как работает бинарный поиск. Сыграем в простую игру: я загадал число от 1 до 100.
| 1 | 2 | 3 | …. | 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
Упражнения:
- Имеется отсортированный список из 128 имен, и вы ищите в нем значение методом бинарного поиска. Какое максимальное количество проверок для этого может потребоваться?
- Предположим, размер списка увеличился вдвое (256 имен). Как изменится максимальное количество проверок?
Ответы:
- 7
- 8
Чтобы не пропускать новые выпуски подписывайтесь на канал @world_hello_ru