Конспект: двоичный поиск и его границы

Понятия

Двоичный поиск - поиск в ОТСОРТИРОВАННОМ массиве за Θ(log n): каждым сравнением выбрасывается половина участка. Требует порядка - на неупорядоченных данных бессмыслен.

Инвариант полуинтервала [lo, hi) - способ писать поиск без ошибок: индексы lo..hi−1 ещё в игре, левее lo и в hi (и правее) ответа нет. Старт lo = 0, hi = len(a); mid = lo + (hi − lo)//2 (защита от переполнения суммы). Сдвиг: a[mid] < x → lo = mid + 1 (плюс-единица - условие завершаемости), a[mid] > x → hi = mid. Цикл идёт, пока lo < hi; hi − lo строго убывает - значит завершается.

Левая граница (lower_bound, bisect_left) - индекс первого элемента ≥ x. Поиск без раннего выхода: a[mid] < x → lo = mid + 1, иначе hi = mid. Строгий знак < тянет к НАЧАЛУ блока повторов. Это позиция вставки x, начало блока вхождений и число элементов строго меньше x.

Правая граница (upper_bound, bisect_right) - индекс первого элемента > x. Тот же поиск с ОДНОЙ заменой: a[mid] <= x → lo = mid + 1, иначе hi = mid. Нестрогий знак ≤ уводит за КОНЕЦ блока. Указывает сразу за последним x.

Число вхождений x = правая − левая (длина полуинтервала [левая, правая)) за Θ(log n). Если левая == правая, элемента x нет.

Двоичный поиск по ответу - поиск не элемента, а числа-ответа (порог, минимум/максимум «такого, что…») по МОНОТОННОМУ предикату ok(x): если ok(x) истинно, то и для всех больших (или всех меньших). Стоимость Θ(log(диапазон) · цена проверки). Сводит задачу «найти оптимум» к «проверить догадку».

Унимодальная функция - строго растёт до вершины, строго падает после. Её максимум ищут сужением отрезка: тернарный поиск (точки 1/3 и 2/3), двоичный по признаку «f(m) < f(m+1)», золотое сечение (одна новая точка на шаг).

Что унести

Двоичный поиск - главный способ превратить Θ(n) в Θ(log n), и весь набор его вариантов - это ОДИН каркас с двумя переключателями.

Мнемоника границ: строгий < - к левому краю (lower), нестрогий ≤ - за правый (upper). Всё остальное в коде идентично. А главный сдвиг мышления урока - переход от «искать в массиве» к «искать в пространстве ответов»: если задача просит минимальное/максимальное «такое, что…», а проверить догадку легко, сведи её к монотонному предикату и получи log вместо перебора.

Вершина унимодальной функции - граница монотонного признака «ещё растёт», поэтому на целых её ищет обычный двоичный поиск: 2·log₂ n вычислений против ≈ 3.4·log₂ n у тернарного (на миллионе - 38 против 64). На вещественных - золотое сечение: 46 вычислений против 104 до точности 10⁻⁹.

Ловушки джокера

lo = mid вместо lo = mid + 1. Зависание на участке из двух элементов: hi − lo не убывает. Плюс-единица - условие завершаемости, а не украшение.

Смешал типы границ (то hi включён, то нет). Промах на один или выход за массив. Определись раз: [lo, hi), правый конец не входит - тогда старт hi = len(a) и сдвиг hi = mid согласованы.

Оставил ранний return mid в поиске границы. Вернётся случайное вхождение из блока, а не левое/правое. Для границы ветка == x должна вести себя как «больше» (левая) или как «меньше» (правая).

Перепутал знак < и ≤. Получишь другую границу; по виду кода не заметно - обе «работают», просто отвечают на разные вопросы.

Прочитал a[p] без проверки p < len(a). Граница может уйти за конец массива (x больше всех) - выход за массив.

Применил поиск по ответу к немонотонному предикату или искал «ровно k». Молча неверный ответ. Сначала докажи ступеньку нет→да; «ровно k» переформулируй в «≥ k».

Ищешь вершину на функции с плато или двумя горбами. Сравнение равных значений не показывает направление, а второй горб поиск просто не заметит - строгая унимодальность обязательна.

Проверь себя

Почему lo = mid + 1 обязательно, а hi = mid - без плюс-единицы?

Что означает инвариант [lo, hi) и почему из-за него старт hi = len(a)?

Чем в коде отличается поиск левой границы от правой и к какому краю блока прилипает каждый?

Как за Θ(log n) сосчитать число вхождений x в отсортированном массиве?

Что обязательно для двоичного поиска по ответу и как из «найти оптимум» получить «проверить догадку»?

Почему вершина унимодальной функции находится обычным двоичным поиском и чем это лучше тернарного?