Бинарный (двоичный) поиск — это алгоритм поиска элемента в уже отсортированном массиве, который на каждом шаге сравнивает искомое значение (ключ) со средним элементом текущего диапазона и отбрасывает ту половину, где ключа заведомо нет. За счет деления пополам он находит элемент за время O(log n) вместо O(n) у перебора. Другое название — метод дихотомии, или «деление пополам».
Содержание
Ниже разберем принцип на пошаговом прогоне руками, напишем итеративную и рекурсивную реализацию на Python с фактическим выводом, оценим сложность и покажем типичные баги с границами и переполнением середины.
Обязательное условие: массив должен быть отсортирован
Бинарный поиск работает только на отсортированной последовательности с доступом к элементу по индексу за O(1) — то есть на массиве или списке Python, а не на связном списке. Логика «ключ меньше среднего, значит он в левой половине» верна лишь тогда, когда элементы упорядочены. На неотсортированных данных алгоритм молча вернет неверный результат, а не ошибку.
Отсюда практический вывод: если данные приходят неотсортированными, перед поиском их надо отсортировать. Сортировка сравнением стоит O(n log n) — дороже одного линейного прохода. Поэтому ради единственного поиска сортировать нет смысла: проще пройти массив линейно. Бинарный поиск выигрывает, когда по одному и тому же массиву ищут многократно: сортировку делают один раз, а каждый последующий поиск стоит O(log n).
Пошаговый прогон руками
Возьмем отсортированный массив из 11 элементов и найдем в нем число 18. Индексы идут с нуля:
индекс: 0 1 2 3 4 5 6 7 8 9 10
значение:1 2 5 7 13 15 16 18 24 28 29
Диапазон задают две границы: low (левая) и high (правая). Середину берем как mid = (low + high) // 2 — целочисленное деление вниз.
- Шаг 1: low=0, high=10, mid=5, arr[5]=15. 15 < 18 — ключ правее, сдвигаем low до mid+1=6.
- Шаг 2: low=6, high=10, mid=8, arr[8]=24. 24 > 18 — ключ левее, сдвигаем high до mid-1=7.
- Шаг 3: low=6, high=7, mid=6, arr[6]=16. 16 < 18 — идем вправо, low=7.
- Шаг 4: low=7, high=7, mid=7, arr[7]=18. Совпадение — возвращаем индекс 7.
Понадобилось 4 сравнения на 11 элементах. Обратите внимание: границу-«проигравшую» мы сдвигаем на mid+1 или mid-1, а не оставляем на mid — это важно, чтобы диапазон гарантированно сужался (к багам вернемся ниже).
Итеративная реализация на Python
Тот же алгоритм в коде. Функция возвращает индекс найденного элемента или -1, если ключа нет:
def binary_search(arr, key):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == key:
return mid
elif arr[mid] < key:
low = mid + 1
else:
high = mid - 1
return -1
data = [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29]
print(binary_search(data, 18)) # 7
print(binary_search(data, 4)) # -1
print(binary_search(data, 29)) # 10Фактический вывод:
7
-1
10
Ключевые моменты: условие цикла low <= high (со знаком «меньше или равно» — иначе теряется последний элемент, см. раздел про баги); середина пересчитывается на каждой итерации; ключа 4 в массиве нет, поэтому возвращается -1; элемент 29 стоит последним и корректно находится по индексу 10.
Чтобы увидеть внутреннее состояние, добавим печать границ на каждом шаге:
def binary_search_trace(arr, key):
low, high = 0, len(arr) - 1
step = 0
while low <= high:
step += 1
mid = (low + high) // 2
print(f"шаг {step}: low={low}, high={high}, mid={mid}, arr[mid]={arr[mid]}")
if arr[mid] == key:
return mid
elif arr[mid] < key:
low = mid + 1
else:
high = mid - 1
return -1
data = [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29]
print("результат:", binary_search_trace(data, 18))Фактический вывод совпадает с ручным прогоном:
шаг 1: low=0, high=10, mid=5, arr[mid]=15
шаг 2: low=6, high=10, mid=8, arr[mid]=24
шаг 3: low=6, high=7, mid=6, arr[mid]=16
шаг 4: low=7, high=7, mid=7, arr[mid]=18
результат: 7
Рекурсивная реализация
Ту же идею можно выразить рекурсией: диапазон передается параметрами, база рекурсии — пустой диапазон (low > high):
def binary_search_rec(arr, key, low, high):
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == key:
return mid
if arr[mid] < key:
return binary_search_rec(arr, key, mid + 1, high)
return binary_search_rec(arr, key, low, mid - 1)
data = [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29]
print(binary_search_rec(data, 18, 0, len(data) - 1)) # 7
print(binary_search_rec(data, 4, 0, len(data) - 1)) # -1Фактический вывод:
7
-1
Результат тот же. Разница в накладных расходах: итеративный вариант работает в постоянной памяти O(1), а рекурсивный тратит стек глубиной до O(log n) кадров. Для больших массивов на Python это обычно некритично (глубина ~log2 n мала), но по умолчанию итеративная версия предпочтительнее — она проще и не рискует упереться в лимит рекурсии.
В стандартной библиотеке Python готовый бинарный поиск есть в модуле bisect (bisect_left, bisect_right): он находит позицию для вставки в отсортированный список. Свою реализацию писать в бою обычно не нужно — но понимать ее устройство важно, чтобы не наделать ошибок в нестандартных задачах (поиск левой/правой границы, поиск по ответу).
Сложность: почему O(log n)
Каждое сравнение отбрасывает примерно половину оставшихся элементов. Значит число шагов — это сколько раз n можно поделить на 2 до единицы, то есть log2(n) (с округлением вверх). Отсюда временная сложность O(log n).
| Размер массива n | Максимум шагов бинарного поиска (~log2 n) | Линейный поиск, O(n) |
|---|---|---|
| 11 | 4 | до 11 |
| 1 000 | 10 | до 1 000 |
| 1 000 000 | 20 | до 1 000 000 |
| 10 000 000 | 24 | до 10 000 000 |
На 10 миллионах элементов бинарному поиску хватает около 24 сравнений — это доли процента от полного перебора. По памяти итеративная версия работает «на месте», O(1): она не копирует массив, а лишь двигает две границы-индекса.
Важная оговорка про сравнение с линейным поиском: O(log n) — это про число сравнений при уже отсортированных данных. Стоимость сортировки O(n log n) в эту оценку не входит и учитывается отдельно, когда решаете, оправдан ли бинарный поиск в вашей задаче.
Типичные баги: границы и переполнение середины
Бинарный поиск короткий, но ошибиться в нем легко. Три классические ловушки.
1. Строгое условие цикла вместо нестрогого. Если написать while low < high вместо while low <= high, то диапазон из одного элемента (когда low == high) не проверяется, и крайний элемент теряется. Прогоним сломанный вариант на том же массиве, ища последний элемент 29:
def binary_search_bug(arr, key):
low, high = 0, len(arr) - 1
while low < high: # БАГ: должно быть low <= high
mid = (low + high) // 2
if arr[mid] == key:
return mid
elif arr[mid] < key:
low = mid + 1
else:
high = mid - 1
return -1
data = [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29]
print(binary_search_bug(data, 29)) # -1 (ошибка: 29 есть в массиве)Фактический вывод — -1, хотя число 29 стоит на индексе 10. Исправление — вернуть нестрогое сравнение low <= high (корректная версия из раздела выше дает 10).
2. Диапазон не сужается — зацикливание. Если «проигравшую» границу двигать на mid, а не на mid+1 / mid-1 (например, писать low = mid вместо low = mid + 1), то на соседних индексах mid может перестать меняться, и цикл повиснет навсегда. Правило простое: элемент с индексом mid уже сравнили, поэтому в следующий диапазон его не включаем — сдвигаем границу за него.
3. Переполнение при вычислении середины. Формула mid = (low + high) // 2 в языках с фиксированной разрядностью целых (C, C++, Java) может переполнить int, если low + high превысит максимум типа. Безопасная запись — mid = low + (high - low) // 2: она дает то же значение, но не складывает две большие величины. В Python целые числа неограниченной точности, поэтому переполнения здесь нет — но привычку писать безопасную формулу стоит держать, если переносите код на языки с фиксированным int. Это известный класс ошибок, всплывший в том числе в библиотечных реализациях.
Выводы
- Бинарный поиск работает только на отсортированном массиве с доступом по индексу и находит элемент за O(log n), отбрасывая половину диапазона на каждом шаге.
- Ради одного поиска сортировать не стоит (сортировка — O(n log n)); выигрыш появляется при многократном поиске по одному массиву.
- Итеративная версия предпочтительнее рекурсивной: та же логика, но память O(1) и нет расхода стека.
- Главные баги — строгое
<вместо<=в условии (теряется крайний элемент), несдвиг границы за mid (зацикливание) и переполнение(low+high)в языках с фиксированным int (лечится формулойlow + (high-low)//2). - В Python готовый бинарный поиск есть в модуле
bisect; свою реализацию полезно понимать для задач с поиском границ и «поиском по ответу».
Где применяется / связь с практикой
Бинарный поиск — базовый кирпич для сотен задач: поиск в отсортированных данных, поиск левой/правой границы вхождения, «бинарный поиск по ответу» в оптимизационных задачах, работа с индексами в базах данных и структурами вроде сбалансированных деревьев. Умение точно расставить границы и не поймать зацикливание проверяют почти на любом техническом собеседовании.
Освойте тему на практике
Разобраться с этим и другими алгоритмами системно, с проверкой решений и разбором сложности, помогает курс Алгоритмы и структуры данных. Если сначала хочется оценить формат и уровень, посмотрите ближайшие бесплатные открытые уроки Otus — там разбирают конкретные задачи вживую.
Смежные темы: Отладка программ: методы и приемы, Квадрат числа в математике и программировании.
FAQ
Можно ли применять бинарный поиск к строкам или другим типам? Да, к любому типу с определенным отношением порядка (строки сравниваются лексикографически, даты — хронологически). Требование одно: массив должен быть отсортирован по тому же критерию, по которому идет сравнение.
Что вернуть, если в массиве несколько одинаковых ключей? Базовая версия вернет индекс какого-то одного из совпадений, не обязательно первого. Для поиска именно левой или правой границы диапазона равных значений используют модификации (bisect_left / bisect_right в Python).
Подходит ли бинарный поиск для связного списка? Нет. Он опирается на доступ к элементу по индексу за O(1), а в связном списке доступ к середине стоит O(n), из-за чего преимущество теряется. Для таких структур берут сбалансированные деревья поиска.
