Как в учебнике
Бинарный поиск находит индекс точного совпадения в массиве, отсортированном по неубыванию. В рассматриваемой реализации элементы и цель — целые числаОткрывается в новой вкладке. Функция возвращает один подходящий индекс или −1, если совпадения нет; первый или последний индекс среди повторов не обещается.
Включительные границы хранятся в left и right. Инвариант: если цель присутствует и ещё не найдена, хотя бы один её индекс находится внутри текущего диапазона. Середина — целая частьОткрывается в новой вкладке (left + right) / 2. Если среднее значение меньше цели, все индексы до середины включительно исключаются; новая левая граница — middle + 1. При большем значении симметрично устанавливается right = middle − 1.
Отсортированность доказывает безопасность исключения. Каждый неуспешный шаг строго уменьшает диапазон, поэтому поиск завершается. При left > right диапазон пуст: инвариант означает, что совпадения нет. На пустом массиве это условие выполнено сразу.
Для массива длины $n\ge2$ худшее время — $O(\log n)$ при постоянной стоимости сравнения и доступа по индексу. Итеративная версия хранит фиксированное число переменных: дополнительная память $O(1)$. Проверка или получение исходной сортировки в эти затраты не входят.
Размер непустого диапазона равен right − left + 1. После неуспешного сравнения остаётся не больше целой частиОткрывается в новой вкладке половины прежнего размера: середина уже исключена. Это связывает завершение с логарифмическойОткрывается в новой вкладке оценкой числа шагов. Неизменность исходного списка существенна для доказательства: если во время поиска переставить элементы или изменить их порядок, ранее исключённая половина уже не обязана оставаться безопасной.
На пальцах
В упорядоченном телефонном справочнике сравнение с фамилией посередине сразу исключает одну половину страниц. После сравнения исключается и сама середина, иначе поиск способен вечно открывать последнюю страницу и называть это настойчивостью. Две закладки сохраняют границы оставшегося участка, поэтому помнить все просмотренные записи не нужно. Порядок записей должен сохраняться на всём протяжении поиска: переклеенные между шагами страницы расторгают договор со справочником без уведомления.
Пример
В отсортированном учебном массиве [2, 5, 8, 12, 17, 23, 31] цель равна 17. Индексы начинаются с нуля. Ниже — состояния того же алгоритма, который записан в коде.
Бинарный поиск на Python
Начальный диапазон
Левая граница 0, правая 6. Все семь позиций ещё возможны.
Шаг 1 из 4: Начальный диапазон
Все шаги текстом
Начальный диапазон
Левая граница 0, правая 6. Все семь позиций ещё возможны.
- Значения
- 25812172331
- Границы
- left = 0текущийright = 6текущий
Середина равна 12
Индекс 3 содержит 12, что меньше 17. Индексы 0–3 исключаются; left = 4.
- Значения
- 2исключён5исключён8исключён12текущий172331
- Остаются
- 17включён23включён31включён
Середина равна 23
В диапазоне 4–6 середина имеет индекс 5. Значение 23 больше цели, поэтому right = 4.
- Значения
- 2исключён5исключён8исключён12исключён1723текущий31исключён
- Остаётся
- 17включён
Совпадение
Границы встретились на индексе 4. Значение 17 равно цели: результат равен 4.
- Значения
- 2исключён5исключён8исключён12исключён17включён23исключён31исключён
- Индекс
- 4включён
Для отсутствующего 18 первые исключения оставляют тот же индекс 4 со значением 17. Следующее сравнение двигает left на 5 при right = 4, и функция возвращает −1. Это обозначение отсутствия, а не пригодный индекс результата: в Python индекс −1 выбрал бы последний элемент списка. Обращение numbers[index] допустимо только после проверки, что поиск действительно нашёл совпадение.
def binary_search(numbers: list[int], target: int) -> int:
left = 0
right = len(numbers) - 1
while left <= right:
middle = (left + right) // 2
value = numbers[middle]
if value == target:
return middle
if value < target:
left = middle + 1
else:
right = middle - 1
return -1
numbers = [2, 5, 8, 12, 17, 23, 31]
print(binary_search(numbers, 17)) # 4
print(binary_search(numbers, 18)) # -1Функция binary_search принимает отсортированный список numbers и цель target, возвращает индекс либо −1 и не изменяет список. На пустом входе right равен −1, поэтому цикл не запускается. Для отсутствующего 18 диапазон в конце пустеет; для одного элемента выполняется не больше одного сравнения с серединой.
Поиск границ повторов, работа с повёрнутым массивом и поиск минимального допустимого числа меняют правило выбора половины. Эти случаи разобраны в закрытом материале «Бинарный поиск на Python». На карточке указаны состав и текущие условия доступа.