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

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

¶История

Первое известное описание бинарного поиска в систематизированном виде принадлежит американскому математику и инженеру Джону Мочли, который в 1946 году в лекциях по информатике предложил алгоритм для поиска в отсортированных списках. Однако практическое применение алгоритма стало возможным только с развитием электронных вычислительных машин. В 1960-х годах бинарный поиск был формализован и включён в стандартные библиотеки алгоритмов. Ключевую роль в популяризации метода сыграла книга Дональда Кнута «Искусство программирования» (том 3, 1973 год), где бинарному поиску посвящён отдельный раздел. В советской информатике алгоритм широко применялся с 1960-х годов в системах управления базами данных и научных расчётах.

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

Алгоритм бинарного поиска применим только к предварительно отсортированным данным (по возрастанию или убыванию). Основные этапы:

1. Определение границ: задаются левая (left) и правая (right) границы интервала поиска. Для массива длиной n начальные значения: left = 0, right = n-1.
2. Вычисление среднего индекса: mid = (left + right) // 2 (целочисленное деление). В некоторых реализациях для избежания переполнения используют формулу mid = left + (right - left) // 2.
3. Сравнение: элемент array[mid] сравнивается с искомым значением key:

• Если array[mid] == key — элемент найден, возвращается его индекс.
• Если array[mid] < key — поиск продолжается в правой половине: left = mid + 1.
• Если array[mid] > key — поиск продолжается в левой половине: right = mid - 1.

1. Повторение: шаги 2-3 выполняются до тех пор, пока left <= right. Если границы смыкаются и элемент не найден, возвращается признак отсутствия (обычно -1).

¶Пример

Для массива [2, 5, 8, 12, 16, 23, 38, 45, 56, 69] и поиска числа 23:

¶Классификация

Бинарный поиск имеет несколько вариантов реализации, различающихся по условиям применения и возвращаемым результатам:

¶По типу данных

• Дискретный бинарный поиск: применяется к статическим массивам фиксированного размера (например, в оперативной памяти).
• Бинарный поиск в отсортированном потоке: используется, когда данные поступают последовательно, но уже отсортированы (например, в файловых системах).
• Бинарный поиск по предикату: применяется для поиска границы, где некоторое условие (предикат) перестаёт выполняться. Например, поиск максимального числа x, для которого f(x) <= target.

¶По поведению при наличии дубликатов

• Поиск первого вхождения (левая граница): когда в массиве несколько одинаковых элементов, возвращается индекс первого из них.
• Поиск последнего вхождения (правая граница): возвращается индекс последнего элемента, равного ключу.
• Стандартный поиск (произвольное): возвращается любой индекс, где элемент равен ключу; при существовании дубликатов поведение не определено.

¶По типу данных и структуре

• Бинарный поиск в массиве: классический вариант для непрерывных массивов.
• Бинарный поиск в связном списке: редко используется из-за необходимости последовательного доступа, что сводит на нет преимущество по скорости.
• Бинарный поиск в дереве: лежит в основе сбалансированных деревьев поиска (AVL, красно-чёрных), где каждый узел хранит ключ, а левое и правое поддеревья — меньшие и большие элементы.

¶Реализация на языках программирования

¶Пример на C

``c int binarySearch(int arr[], int size, int target) { int left = 0, right = size - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; } ``

¶Пример на Python

``python def binary_search(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1 ``

¶Сложность

• Временная сложность: в худшем и среднем случаях O(log n), в лучшем (при попадании в середину) O(1).
• Пространственная сложность: O(1) для итеративной версии, O(log n) для рекурсивной (из-за стека вызовов).

Сравнение с другими методами поиска:

¶Применение

¶В информатике и программировании

• Поиск в отсортированных массивах (например, в словарях, каталогах, базах данных с индексом).
• Реализация функций стандартной библиотеки (например, bsearch() в C, bisect в Python, Arrays.binarySearch() в Java).
• Поиск корней уравнений методом бинарного поиска (бисекции) — если функция монотонна на интервале.
• В алгоритмах сжатия данных (например, поиск кода по таблице).
• В игровых движках для ускорения поиска объектов по сетке.

¶В научных расчётах

• Решение уравнений с одной переменной (бисекция) — численный метод, не требующий вычисления производной.
• Оптимизация параметров модели, когда проверяемое значение монотонно зависит от параметра.

¶В базах данных

• Бинарный поиск лежит в основе индексации по B-деревьям (B-Tree), используемым в большинстве реляционных СУБД (например, PostgreSQL, MySQL).
• Поиск по первичному ключу в таблицах.

¶В повседневных алгоритмах

• Поиск в телефонных книгах, словарях, энциклопедиях (все предварительно отсортированы по алфавиту).
• Оптимизация загрузки оборудования — подбор подходящего размера буфера, времени ожидания.
• В криптографии — поиск по секретному ключу на основе «угадывания» с помощью временной боковой атаки.

¶Ошибки и подводные камни

Несмотря на кажущуюся простоту, бинарный поиск подвержен ряду ошибок при реализации:

• Выход за границы массива при вычислении mid, особенно если left + right превышает максимальное значение целого числа (в языках с фиксированной разрядностью — C, C++, Java). Используется формула mid = left + (right - left) / 2.
• Бесконечный цикл при неправильном обновлении границ (например, left = mid вместо left = mid + 1, или right = mid вместо right = mid - 1).
• Неравномерное разделение при работе с плавающими числами — необходимо учитывать погрешность.
• Отсутствие проверки на пустой массив — может вызвать деление на ноль при вычислении mid.
• Неправильная обработка дубликатов — если требуется найти именно первое или последнее вхождение, стандартный бинарный поиск может вернуть любое из них.

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

• По данным исследований, проведённых в начале 2000-х годов, около 90% профессиональных программистов неспособны написать правильную реализацию бинарного поиска с первой попытки из-за граничных условий.
• В 2006 году в языке Java была обнаружена ошибка в реализации бинарного поиска в классе Arrays (COLT-1456), связанная с переполнением при вычислении среднего индекса. Ошибка была исправлена только через несколько лет.
• Бинарный поиск является частным случаем более общего метода — поиска делением пополам (binary search on a monotonic function), который применяется не только к массивам, но и к любым монотонным функциям.
• В российских учебниках по информатике для средней школы (например, Босова Л.Л., «Информатика») бинарный поиск традиционно изучается в 9-11 классах как один из основных алгоритмов обработки массивов.

¶Источники

• Кнут Д. Искусство программирования. Том 3: Сортировка и поиск. — М.: Вильямс, 2007.
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — М.: Вильямс, 2016.
• Бентли Д. Жемчужины программирования. — СПб.: Питер, 2007.
• Bosova L.L. Informatics: textbook for 9th grade. — Moscow: Prosveshchenie, 2020.
• Wikipedia: Binary search algorithm (accessed 2025).