Бинарный поиск (Binary search)

Алгоритм бинарного поиска находит элемент в отсортированном списке.

Рассмотрим пример. Сравним искомое число и первый элемент списка. Предположим, мы выясняли, что искомое число меньше первого элемента массива. Так как первый элемент массива, если массив отсортирован по возрастанию, является наименьшем, то можно сразу сделать вывод, что искомого числа в массиве нет и просматривать его дальше нет смысла.

Применим ту же логику, но сравним искомое число и элемент в середине списка. Если элемент равен искомому числу, то задача решена, но если не равен и искомое число больше элемента из середины, то очевидно, что имеет смысл проверять только вторую половину массива — числа справа от числа которое только что проверили.

Это и есть основная идея бинарного поиска — проверять не все элементы массива, а использовать отсортированность массива для сокращения количества проверок.

Псевдокод

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

Как и в случае линейного поиска, признаком отсутствия элемента в массиве служи число -1.

алгоритм бинарный_поиск(массив, искомый_элемент)
начало
  индекс_начала = 0
  индекс_конца = последний элемент массива
  
  пока индекс_начала <= индекс_конца
    индекс_середины = находим середину между индекс_начала и индекс_конца
    если элемент с индексом в середине равен искомому элементу
      то возвращаем индекс_середины и завершаем алгоритм
    
    если элемент с индексом в середине больше искомого
      то индекс_начала = индекс_середины + 1
    
    если элемент с индексом в середине меньше искомого
      то индекс_конца = индекс_середины - 1
   
  возвращаем -1 и завершаем алгоритм 
конец

Реализация на Python

def binary_search(lst, item):
  """
    Функция возвощает индекс элемента item в списке lst
    или -1 если элемент не найден.
  """

  first = 0
  last = len(lst) \- 1
  
  while first <= last:
    mid = first + (last - first) // 2
    if lst[mid] == item:
      return mid

    if lst[mid] < item:
      first = mid + 1
    else:
      last = mid - 1
  return -1

Условия

Принципиальное требование для бинарного поиска — сортировка массива. Поэтому бинарный поиск невозможен в неупорядоченных коллекциях с элементами которые нельзя сравнить друг с другом. Если массив неотсортированный то можно использовать только линейный поиск.

Второй важный момент — коллекция должна быть с произвольным доступом. Если это требование не будет выполнено, то эффективность бинарного поиска будет меньше возможной.

Сложность

Бинарный поиск, в худшем случае, проверяет только $lo{g}_2(n)$ элементов, следовательно, сложность тоже будет равна $\mathcal{O}(lo{g}_2(n))$. Последовательный поиск в несортированном массиве, в худшем случае, проверяет все элементы и его сложность $\mathcal{O}(n)$.

Алгоритм не требует дополнительной памяти пропорциональной входному массиву, поэтому его сложность по памяти равна $\mathcal{O}(1)$.

Ссылки

• Грокаем алгоритмы. Адитья Бхаргава. Питер. 2018. Глава 1. Знакомство с алгоритмами. Бинарный поиск

Ссылки на эту заметку

• Линейный поиск (Linear search)

Эта заметка на GitHub

Обсудить на форуме