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

Алгоритм

  1. Найдите средний элемент списка.
  2. Если искомый элемент равен среднему элементу, возвращаем его.
  3. Если искомый элемент больше среднего элемента, вся нижняя половина списка и средний элемент могут быть исключены из дальнейшего рассмотрения.
  4. Если искомый элемент меньше среднего элемента, вся верхняя половина списка и средний элемент могут быть исключены из дальнейшего рассмотрения.
  5. Затем мы можем повторить процесс с верхней или нижней половиной в зависимости от того, где находится элемент, начав со среднего элемента и сравнив его с тем, что мы ищем. Опять же, мы либо находим его, либо делим список пополам, тем самым устраняя еще одну большую часть нашего возможного пространства поиска.

Рекурсивная реализация бинарного поиска

Итеративное внедрение бинарного поиска

Анализ сложности

  • Временная сложность: O (log n)
  • Пространственная сложность: O(1), так как это постоянное космическое решение.