Бинарный поиск: инвариант вместо угадывания

Бинарный поиск обычно объясняют так: «ищем число в отсортированном массиве, каждый раз отбрасываем половину». Объяснение верное и почти бесполезное — потому что в задачах нужно не «найти число», а найти границу, и вот тут начинаются +1, -1 и бесконечные циклы.

Разберём подход, при котором путать нечего.

Сначала инвариант, потом код

Инвариант — условие, которое верно всегда: до цикла, после каждой итерации и после выхода.

Заведём две границы и договоримся, что про них известно. Скажем, ищем в отсортированном массиве последнее число, не превосходящее $x$:

$$a_l \le x \quad\text{и}\quad a_r > x$$

Это и есть инвариант. Дальше код пишется механически: пока между границами есть что-то ещё, берём середину и сдвигаем ту границу, для которой условие сохранится.

int l = -1, r = n;              // границы заведомо вне массива
while (r - l > 1) {
    int mid = l + (r - l) / 2;
    if (a[mid] <= x) l = mid;   // инвариант для l сохранён
    else r = mid;               // инвариант для r сохранён
}
// l — последний индекс, где a[l] <= x; r — первый, где a[r] > x

Обратите внимание: l и r начинаются вне массива. Это не небрежность, а необходимость: инвариант должен быть верен с самого начала, а гарантировать a[0] <= x мы не можем. Фиктивные границы решают вопрос — про них инвариант считается выполненным по определению.

Цикл всегда завершается: l < mid < r, значит r - l строго убывает. Никакого «а вдруг зациклится» здесь не бывает.

Что именно найдено

После выхода r - l == 1, то есть границы стали соседними. По инварианту a[l] <= x, а a[r] > x — значит, между ними и проходит та самая граница.

Поменяйте знак в условии, и поиск начнёт находить другое:

Условие в if	l — последний, где	r — первый, где
a[mid] <= x	$a_l \le x$	$a_r > x$
a[mid] < x	$a_l < x$	$a_r \ge x$

Вторая строка — это то, что в C++ называется lower_bound, первая — upper_bound. Один и тот же код, разница в одном символе.

Отсюда способ считать вхождения: количество элементов, равных $x$, — это разность двух границ.

int count = upper_bound(a.begin(), a.end(), x) - lower_bound(a.begin(), a.end(), x);

Границы: правило, которое ловится только стрессом

Начальные значения l и r зависят от того, в какой переменной вы ждёте ответ.

Границы никогда не совпадают с ответом сразу: l только растёт, r только убывает, и ни одна из них не может выйти за начальное значение другой. Значит:

• если ответ должен оказаться в l, то l обязана иметь возможность добраться до любого индекса — берём l = -1, r = n;
• если ответ ждём в r — тогда l = -1, r = n - 1 не годится, нужно чтобы r могла дойти до нуля.

Проще запомнить так: фиктивные границы ставятся с той стороны, где ответа быть не может. Если ответ в l, фиктивна левая граница; если в r — правая.

Ошибка здесь коварна тем, что на примерах из условия не проявляется: там ответ обычно в середине массива. Поймать её можно только стресс-тестом на маленьких массивах, включая случаи «ответ на первой позиции» и «ответа нет вовсе».

Переполнение середины

(l + r) / 2 при больших границах переполняется. Безопасная форма — l + (r - l) / 2: она считает то же самое, но промежуточное значение не выходит за пределы диапазона.

В массиве это неважно — индексы малы. В поиске по ответу, где границы бывают до $10^{18}$, — важно.

Почему логарифм

Длина промежутка делится пополам на каждом шаге: $n$, $n/2$, $n/4$, …. Итераций нужно столько, чтобы $2^k \ge n$, то есть $k = \lceil \log_2 n \rceil$.

Для $n = 10^9$ это меньше 30 шагов, для $n = 10^{18}$ — 60. Именно поэтому в задачах с ограничением на число запросов ровно 60 при $N$ до $10^{18}$ можно не гадать, что от вас хотят.