Бинарный поиск прост по идее, но на практике это один из самых «ошибкоёмких» алгоритмов. В этой теме разберём ловушки на границах, первое и последнее вхождение при дубликатах и стандартный модуль bisect.
![Нижняя и верхняя граница для 2 в [1, 2, 2, 2, 5, 8]](img/lessons/algorithms/binary-search-pitfalls-bounds.svg)
Границы: замкнутый и полуинтервал
В прошлой теме мы использовали замкнутый интервал [lo, hi] (hi = len(a) - 1, lo <= hi, hi = mid - 1). Для дубликатов и «места вставки» удобнее полуинтервал [lo, hi): hi = len(a), lo < hi, hi = mid. У каждого шаблона свой инвариант, а смешение даёт IndexError, бесконечный цикл или ошибку на единицу. Правило: выберите один шаблон и держите все три части (начало, условие, обновление) вместе.
Первое и последнее вхождение: lower_bound и upper_bound
lower_bound(a, x) — первая позиция i, где a[i] >= x; upper_bound(a, x) — первая, где a[i] > x. Обе возвращают позицию в диапазоне 0..len(a) (не ячейку) и даже при отсутствии x указывают место, сохраняющее порядок. Первое вхождение — lower_bound, последнее — upper_bound - 1, количество — upper_bound - lower_bound. Наличие x проверяется так: i < len(a) and a[i] == x.
