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


Deprecated: Function create_function() is deprecated in /home/worldhel/public_html/wp-content/plugins/codecolorer/lib/geshi.php on line 4698

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

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

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

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

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

123….100

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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