Бинарный поиск
Описание
Бинарный поиск — это алгоритм поиска элемента в отсортированном массиве путём многократного деления интервала поиска пополам. На каждом шаге алгоритм сравнивает средний элемент массива с целевым значением и исключает половину, в которой искомый элемент заведомо отсутствует.
Зачем это нужно
Бинарный поиск — один из фундаментальных алгоритмов, который постоянно используется в веб-разработке: поиск по отсортированным данным, автодополнение, поиск по индексам баз данных, реализация функции bisect. Знание бинарного поиска помогает понимать, как работают индексы в базах данных и почему они такие быстрые.
Визуализация
Как работает алгоритм
Бинарный поиск основан на принципе «разделяй и властвуй». Вместо того чтобы проверять каждый элемент массива по очереди (как это делает линейный поиск), алгоритм каждый раз сокращает область поиска вдвое.
1. Определение границ поиска
Устанавливаем два указателя: left (начало массива) и right (конец массива). Эти указатели определяют текущий диапазон, в котором мы ищем целевой элемент.
2. Нахождение среднего элемента
Вычисляем индекс среднего элемента: mid = left + (right - left) / 2. Использование такой формулы вместо (left + right) / 2 предотвращает переполнение целочисленного типа при работе с большими массивами.
3. Сравнение с целевым значением
Сравниваем arr[mid] с целевым значением. Возможны три варианта:
- arr[mid] == target — элемент найден, возвращаем индекс mid.
- arr[mid] < target — целевой элемент находится в правой половине. Сдвигаем left = mid + 1.
- arr[mid] > target — целевой элемент находится в левой половине. Сдвигаем right = mid - 1.
4. Повторение или завершение
Повторяем шаги 2–3, пока left ≤ right. Если указатели пересеклись (left > right), значит элемент отсутствует в массиве — возвращаем -1.
Шаг 1: left=0, right=6, mid=3 → arr[3]=7 == 7. Найдено за 1 шаг!
Для сравнения: при линейном поиске в массиве из 1 000 000 элементов бинарный поиск найдёт элемент максимум за 20 шагов (log₂ 1 000 000 ≈ 20).
Сложность
Анализ сложности
Временная сложность
O(1) — лучший случай, когда целевой элемент оказывается ровно посередине массива с первого шага.
O(log n) — средний случай. На каждом шаге алгоритм отбрасывает половину оставшихся элементов. Для массива из n элементов потребуется не более ⌈log₂ n⌉ сравнений.
O(log n) — худший случай. Элемент находится на краю массива или отсутствует вовсе, но даже тогда количество шагов логарифмически зависит от размера массива.
Пространственная сложность
O(1) — итеративная реализация использует только несколько переменных (left, right, mid), не зависящих от размера входных данных.
O(log n) — рекурсивная реализация использует стек вызовов глубиной log₂ n.
Линейный поиск имеет сложность O(n) — в худшем случае проверяет все n элементов. Бинарный поиск сокращает это до O(log n). Для массива из 1 миллиарда элементов: линейный поиск — до 1 000 000 000 шагов, бинарный — до 30 шагов.
Пример кода
function binarySearch(arr: number[], target: number): number {let left = 0;let right = arr.length - 1;while (left <= right) {// Find the middle indexconst mid = Math.floor((left + right) / 2);if (arr[mid] === target) {return mid; // Found the target} else if (arr[mid] < target) {left = mid + 1; // Search right half} else {right = mid - 1; // Search left half}}return -1; // Target not found}// Usage exampleconst sortedArray = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];const result = binarySearch(sortedArray, 23);console.log(result); // 5 (index of 23)
Примеры использования в реальных задачах
Поиск в отсортированных данных
Любой отсортированный набор данных — идеальный кандидат для бинарного поиска. Словари, телефонные книги, справочники — все они используют принцип деления пополам.
Индексы в базах данных (B-Tree)
B-деревья, лежащие в основе индексов PostgreSQL, MySQL и других СУБД, используют бинарный поиск на каждом уровне дерева для быстрого нахождения нужной страницы. Именно поэтому индексированный поиск по ID работает за миллисекунды даже в таблицах с миллиардами строк.
Функция bisect в Python
Модуль bisect в стандартной библиотеке Python реализует бинарный поиск для вставки элементов в отсортированный список с сохранением порядка. Используется для приоритетных очередей, бегущих медиан и оконных функций.
Автодополнение и поиск по префиксу
При вводе текста в строку поиска система находит нижнюю и верхнюю границу подходящих вариантов с помощью бинарного поиска по отсортированному словарю.
Определение границ (lower_bound / upper_bound)
Бинарный поиск используется для нахождения первого элемента ≥ target (lower_bound) и первого элемента > target (upper_bound). Это основа для реализации множеств и диапазонных запросов в C++ STL.
Бинарный поиск по ответу
Парадоксальное применение: когда прямое решение сложно, но можно проверить «достаточно ли хорош» предполагаемый ответ. Применяется в задачах на оптимизацию: минимальное время, максимальное расстояние, минимальный вес — если ответ можно проверить за полиномиальное время.