Двоичный поиск

Двоичный поиск (также известный как бинарный поиск, метод половинного деления, дихотомия) — это алгоритм поиска элемента в упорядоченном (отсортированном) массиве данных, который на каждом шаге делит область поиска пополам, сравнивая искомое значение со средним элементом текущего интервала. Двоичный поиск является классическим примером алгоритма «разделяй и властвуй» (divide and conquer) и обладает логарифмической временной сложностью O(log n), что делает его значительно более эффективным, чем линейный поиск (O(n)) для больших наборов данных.

История

Идея двоичного поиска впервые была описана в древних математических текстах. Принцип последовательного деления отрезка пополам для нахождения корня уравнения (метод бисекции) был известен ещё математикам Древнего Вавилона и Древней Греции. В контексте вычислительной техники алгоритм впервые был явно описан в 1946 году американским математиком и пионером программирования Джоном Мокли (John Mauchly) в его лекциях. Однако широкое распространение и формальное описание алгоритм получил после публикации в 1962 году книги Дональда Кнута «Искусство программирования» (The Art of Computer Programming), где двоичный поиск был подробно разобран.

Несмотря на кажущуюся простоту, реализация двоичного поиска часто содержит скрытые ошибки, наиболее известная из которых — переполнение целочисленного типа при вычислении среднего индекса (mid = (low + high) / 2). Эта ошибка была обнаружена и исправлена в 2006 году в реализации Java.

Принцип работы

Алгоритм двоичного поиска работает только на предварительно отсортированном массиве. Основная идея заключается в следующем:

1. Определяются границы области поиска: левая (low) и правая (high), изначально равные первому и последнему индексам массива.
2. Вычисляется индекс среднего элемента: mid = low + (high — low) / 2 (безопасный способ избежать переполнения).
3. Сравнивается значение среднего элемента (array[mid]) с искомым значением (target):

• Если array[mid] == target, поиск завершён успешно.
• Если array[mid] > target, то искомый элемент находится в левой половине массива. Правая граница смещается: high = mid — 1.
• Если array[mid] < target, то искомый элемент находится в правой половине массива. Левая граница смещается: low = mid + 1.

1. Шаги 2–3 повторяются до тех пор, пока не будет найден элемент или пока левая граница не станет больше правой (low > high), что означает отсутствие элемента в массиве.

Реализация

Итеративная версия

Итеративная реализация использует цикл и является наиболее распространённой и эффективной.

```python def binary_search(arr, target): low = 0 high = len(arr) — 1

while low <= high: mid = low + (high — low) // 2 # Безопасное вычисление середины guess = arr[mid]

if guess == target: return mid # Элемент найден, возвращаем индекс if guess > target: high = mid — 1 # Ищем в левой половине else: low = mid + 1 # Ищем в правой половине

return -1 # Элемент не найден ```

Рекурсивная версия

Рекурсивная реализация более декларативна, но может потреблять больше памяти из-за стека вызовов.

```python def binary_search_recursive(arr, target, low, high): if low > high: return -1 # Базовый случай: элемент не найден

mid = low + (high — low) // 2

if arr[mid] == target: return mid elif arr[mid] > target: return binary_search_recursive(arr, target, low, mid — 1) else: return binary_search_recursive(arr, target, mid + 1, high) ```

Характеристики и сложность

• Временная сложность:
• Лучший случай: O(1) — элемент находится в середине на первой итерации.
• Средний и худший случай: O(log n) — количество итераций пропорционально логарифму длины массива по основанию 2.
• Пространственная сложность:
• Итеративная версия: O(1) — используется фиксированное количество дополнительных переменных.
• Рекурсивная версия: O(log n) — из-за глубины рекурсии (стек вызовов).
• Требования к данным: Массив должен быть отсортирован по возрастанию (или убыванию) в соответствии с используемым оператором сравнения.

Классификация и варианты

Двоичный поиск по ответу

Этот вариант используется не для поиска элемента в массиве, а для нахождения граничного значения, при котором выполняется некоторое условие. Например, поиск наименьшего числа X, такого что f(X) >= K. Алгоритм применяется в задачах оптимизации, численных методах и машинном обучении.

Двоичный поиск с вставкой (Lower Bound / Upper Bound)

Вместо проверки на равенство, эти варианты находят позицию, куда можно вставить элемент, не нарушая порядок сортировки:

• Lower Bound (нижняя граница): Первая позиция, где элемент может быть вставлен, чтобы массив остался отсортированным (первый индекс, где arr[index] >= target).
• Upper Bound (верхняя граница): Первая позиция, где arr[index] > target.

Троичный поиск (Ternary Search)

Алгоритм, который делит область поиска на три части, а не на две. Используется для поиска максимума или минимума унимодальной функции (функции, которая сначала возрастает, а затем убывает, или наоборот). Временная сложность — O(log₃ n), что на практике часто медленнее двоичного поиска из-за большего количества вычислений на каждом шаге.

Применение

Двоичный поиск является фундаментальным алгоритмом и используется во множестве областей:

• Поиск в базах данных: Поиск по индексу (B-деревья, хеш-таблицы) часто основан на принципе двоичного поиска.
• Отладка программ: Метод «двоичного поиска» в коде (биссекция) — поиск первого коммита, вызвавшего ошибку, путём последовательного деления истории коммитов пополам (например, команда git bisect).
• Численные методы: Метод бисекции для нахождения корней уравнений.
• Компьютерная графика: Алгоритмы трассировки лучей, поиск ближайшего объекта.
• Стандартные библиотеки: Функции binary_search, lower_bound, upper_bound в C++ STL, bisect в Python, Arrays.binarySearch() в Java.
• Сжатие данных: Алгоритмы кодирования (например, арифметическое кодирование) используют принцип деления интервала.
• Игры: Поиск пути (A*), принятие решений ИИ.

Интересные факты

• Несмотря на то, что алгоритм был описан в 1946 году, первая правильная реализация двоичного поиска без ошибок была опубликована только в 1962 году.
• В 2006 году в реализации двоичного поиска в Java была обнаружена ошибка переполнения, которая могла приводить к вылету программы при поиске в массивах размером более 2³⁰ элементов.
• Двоичный поиск является одним из немногих алгоритмов, чья эффективность напрямую зависит от предварительной сортировки данных. Если данные не отсортированы, его применение невозможно.
• Алгоритм является основой для многих более сложных структур данных, таких как деревья поиска (бинарные деревья, AVL-деревья, красно-чёрные деревья).

Источники

1. Кнут Д. Э. Искусство программирования. Том 3. Сортировка и поиск. — М.: Вильямс, 2015.
2. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — М.: Вильямс, 2013.
3. Седжвик Р. Фундаментальные алгоритмы на C++. Анализ/Структуры данных/Сортировка/Поиск. — М.: ДиаСофт, 2011.
4. Bentley J. Programming Pearls. — Addison-Wesley Professional, 1999.