Бинарный поиск
Поиск в отсортированном массиве, который на каждом шаге исключает половину диапазона.
Понять идею до написания кода
Сначала зафиксируйте диапазон, в котором ещё может находиться ответ. Сравните цель со средним элементом и отбросьте половину, которая точно не подходит. Повторяйте, пока цель не найдена или допустимый диапазон не опустеет.
Корректность держится на инварианте: если ответ существует, после каждого шага он остаётся внутри активного диапазона.
Как это работает
Время и память
Для статического отсортированного массива поиск занимает O(log n). Если тот же массив используется как динамическая таблица, вставка с сохранением порядка требует O(n) из-за сдвига элементов.
Код без скрытых шагов
def binary_search(items, target):
left, right = 0, len(items) - 1
while left <= right:
mid = left + (right - left) // 2
if items[mid] == target:
return mid
if items[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1Частые ошибки
Запускать поиск на неотсортированных данных.
Неправильно обновлять границы и получать бесконечный цикл.
Путать поиск любого совпадения с поиском первой или последней позиции.
Возвращать -1 по привычке, когда задаче нужна позиция вставки или граница диапазона.
Источники и их роли
Источники решают разные учебные задачи: статья даёт переносимые соревновательные шаблоны, а книга объясняет, почему они корректны и где заканчивается их эффективность.
Начните с полуинтервала и явного предиката. Затем переходите к lower/upper bound, поиску границы и бинарному поиску по ответу.
Рассматривайте rank и как индекс найденного ключа, и как позицию вставки. Поиск требует логарифмического числа сравнений, но вставка с сохранением порядка остаётся O(n).
Сначала выберите точный контракт ответа и сформулируйте инвариант границ; только после этого переносите подходящий шаблон в код.