Бинарный поиск: как работает

Бинарный поиск — один из самых полезных приёмов в программировании. Ниже — полная теория из курса «Кружок 102»: как он устроен, почему работает за логарифм и как искать им ответ.

Представь, что ты ищешь слово в бумажном словаре. Ты не листаешь страницы подряд с первой — ты открываешь словарь примерно посередине, смотришь, какая там буква, и сразу понимаешь, в какой половине искать дальше. Потом повторяешь то же самое с этой половиной. За десяток таких шагов ты находишь любое слово среди сотен тысяч. Это и есть бинарный поиск: способ находить нужное значение в отсортированных данных, отбрасывая на каждом шаге половину вариантов.

Наивный поиск элемента в массиве из n чисел — это перебор, который в среднем требует порядка n/2 сравнений, а в худшем случае — все n. Бинарный поиск делает то же самое за O(log n) сравнений. Разница огромная: для массива в миллиард элементов линейный поиск в худшем случае сделает миллиард шагов, а бинарный — около 30. Именно поэтому бинарный поиск — один из самых используемых приёмов в олимпиадном программировании, причём далеко не только для поиска элемента в массиве: гораздо чаще на олимпиадах он применяется как «бинарный поиск по ответу» — способ находить оптимальное значение, даже если явной отсортированной последовательности нет вообще.

Идея: монотонность и предикат

Ключевая вещь, без которой бинарный поиск не имеет смысла, — это монотонность. У нас есть некоторое условие (предикат) P(x), которое для маленьких x ложно, а начиная с некоторого порога — истинно (и дальше остаётся истинным). Проще говоря, если выписать значения предиката подряд, получится последовательность вида

false, false, false, … , false, true, true, … , true

без «дырок» и «перескоков» — то есть монотонная. Бинарный поиск — это способ найти границу перехода false → true за логарифмическое число проверок предиката, не проверяя все значения подряд.

Самый очевидный пример такого предиката: «a[i] ≥ x» для отсортированного по неубыванию массива a. Но предикат может быть и куда менее очевидным: «можно ли перевезти весь груз k грузовиками грузоподъёмности x», «хватит ли времени t, чтобы решить все задачи», «можно ли расставить коров по стойлам так, чтобы минимальное расстояние между соседними было не меньше d». Как только вы доказали, что такой предикат монотонен по параметру, можно тем же самым алгоритмом найти точку перехода — а значит, и оптимальный ответ.

Классическая схема на полуинтервале

Самая надёжная реализация — та, где инвариант формулируется предельно чётко и не допускает двусмысленности. Возьмём полуинтервал [l, r), для которого поддерживается инвариант:

• P(l) ложно (или l — это условная «граница снизу», левее которой всё гарантированно false),
• P(r) истинно (или r — условная «граница сверху», правее которой всё гарантированно true).

То есть искомая граница — первое x, при котором P(x) = true — всегда лежит где-то в (l, r]. Мы сужаем этот полуинтервал, пока r - l не станет равно 1 — тогда r и есть ответ.

Границы стоит выбирать так, чтобы инвариант заведомо выполнялся с самого начала: l — это «заведомо-false» граница (берём её на 1 меньше минимально возможного ответа, чтобы P(l) точно было ложно), а r — «заведомо-true» граница (любое значение, которое уж точно удовлетворяет предикату). Образец такого выбора — пример с книгами ниже: там l = 0 (раздать по 0 страниц нельзя — false) и r = сумма всех страниц (одному курьеру можно отдать всё — true).

// ищем наименьшее x, для которого P(x) истинно
// инвариант: P(l) == false, P(r) == true
long long l = L - 1, r = R; // L, R — границы диапазона поиска
while (r - l > 1) {
    long long m = l + (r - l) / 2; // защита от переполнения
    if (P(m)) r = m;
    else      l = m;
}
// ответ: r

Почему это работает и почему именно так выбраны границы захвата — стоит проговорить по шагам.

Корректность. Инвариант сохраняется на каждой итерации по построению: если P(m) истинно, мы можем «подтянуть» правую границу к m, потому что m по-прежнему удовлетворяет условию «здесь и правее — true». Если P(m) ложно — аналогично подтягиваем левую границу. Инвариант никогда не нарушается, а значит в конце, когда r - l = 1, гарантированно P(l)=false и P(r)=true — это и есть искомая граница перехода.

Почему интервал обязательно сузится до одной точки, а не зациклится. На каждом шаге мы берём m строго между l и r (это возможно ровно до тех пор, пока r - l > 1, поэтому в условии цикла стоит именно это), и после присваивания расстояние r-l становится либо m-l, либо r-m. Обе величины строго меньше исходного r-l и не превосходят ⌈ (r-l)/2 ⌉ (скобки ⌈·⌉ — округление вверх), то есть интервал каждый шаг сжимается примерно вдвое: зацикливание невозможно. Отсюда и оценка сложности.

Сложность. Если исходная длина интервала n, то после k шагов она не превышает n / 2^k. Условие останова — длина 1, значит число шагов k ≈ log₂ n. Отсюда O(log n) обращений к предикату (плюс стоимость самого предиката — если, скажем, для проверки P(x) нужно пройтись по массиву за O(n), то весь бинарный поиск по ответу будет стоить O(n log n)).

Почему в схеме используется полуинтервал, а не привычные l <= r со строгими l = m+1/r = m-1? Потому что при таком варианте очень легко ошибиться на границах и получить либо бесконечный цикл, либо ответ, сдвинутый на единицу. Схема с [l, r) и инвариантом «слева всегда false, справа всегда true» не имеет неоднозначностей: middle всегда строго внутри, а условие r - l > 1 гарантирует прогресс. Это ровно та причина, по которой такую формулировку рекомендует, например, Algorithmica: явный инвариант избавляет от необходимости каждый раз передумывать, <= там или <, m+1 или m.

Классический поиск элемента и lower_bound/upper_bound

Если задача — просто найти элемент x в отсортированном массиве, предикат естественный: P(i) = [a[i] ≥ x]. Точка перехода даёт первый индекс, где a[i] ≥ x — это и есть то, что в C++ называется lower_bound. Аналогично upper_bound ищет первый индекс, где a[i] > x. Разница между ними принципиальна, если в массиве есть повторяющиеся элементы: lower_bound даёт начало «блока» равных x, upper_bound — конец, и upper_bound(x) - lower_bound(x) — это ровно количество вхождений x в массив.

#include <algorithm>
int idx = std::lower_bound(a.begin(), a.end(), x) - a.begin();

В Python то же самое делает модуль bisect:

import bisect
idx = bisect.bisect_left(a, x)   # аналог lower_bound
idx2 = bisect.bisect_right(a, x) # аналог upper_bound

Стоит понимать, что и bisect, и lower_bound внутри реализуют ровно тот же алгоритм с инвариантом на полуинтервале — писать «руками» их приходится, когда предикат не такой прямолинейный, как сравнение с массивом, либо когда языковая библиотека не подходит по формату данных (например, когда предикат вычисляется, а не читается из массива).

Бинарный поиск по ответу

Это тот случай, где по-настоящему раскрывается сила идеи. Многие оптимизационные задачи имеют вид «найдите минимальное x, при котором возможно то-то» или «найдите максимальное x, при котором выполняется то-то». Если функция «возможно ли при данном x» монотонна по x — задачу почти всегда выгоднее решать не напрямую, а через бинарный поиск: подставляем кандидат x=m, проверяем предикат за какое-то разумное время, и по результату проверки сужаем диапазон.

Классический пример — задача «распилить брёвна на k частей минимальной длины не меньше x, максимизировать x» или «раздать книги k курьерам так, чтобы минимизировать максимальную нагрузку одного курьера». Во втором случае предикат такой: «можно ли раздать книги k курьерам так, чтобы у каждого было не больше x страниц» — это легко проверить жадно за линейное время, и предикат монотонен: если получилось уместить в лимит x, то получится и в любой x' > x. Значит бинарным поиском по x находим минимальный допустимый лимит за O(n log(sum)) вместо явного перебора всех значений лимита.

Вот это решение целиком (книги раздаются подряд идущими блоками):

// предикат: можно ли раздать книги k курьерам,
// чтобы каждый нёс не больше x страниц?
bool can(const vector<int>& pages, int k, long long x) {
    int couriers = 1;                   // первый курьер уже «открыт»
    long long cur = 0;                  // сколько страниц он уже несёт
    for (int p : pages) {
        if (p > x) return false;        // одна книга толще лимита — никак
        if (cur + p <= x) cur += p;     // влезает текущему курьеру
        else { couriers++; cur = p; }   // открываем следующего
    }
    return couriers <= k;
}

long long solve(const vector<int>& pages, int k) {
    long long l = 0, r = 0;             // P(0) = false, P(сумма) = true
    for (int p : pages) r += p;
    while (r - l > 1) {
        long long m = l + (r - l) / 2;
        if (can(pages, k, m)) r = m;
        else l = m;
    }
    return r;                           // минимальная максимальная нагрузка
}

Заметь, как чётко разделились роли: вся «умность» — в жадном предикате can, а бинарный поиск вокруг него — дословно та же заготовка, что и выше.

Здесь важно каждый раз доказывать монотонность отдельно — это не автоматическая вещь, а свойство конкретной задачи, и именно доказательство монотонности является главной идейной частью решения. Само по себе применение бинарного поиска — механическая часть.

Две зеркальные заготовки. Заготовка выше ищет первый true (минимальный x, при котором предикат истинен) — это последовательность вида false … false, true … true. Но примерно половина задач по ответу имеет зеркальную монотонность true … true, false … false, и там нужно найти последний true (максимальный x, при котором ещё возможно): «провода» — максимальная длина отрезка, «коровы в стойла» — максимальное минимальное расстояние, «дипломы» — максимальная сторона квадрата. Для такого случая внутренность цикла зеркальная:

if (P(m)) l = m; else r = m; // ответ l

Правило выбора заготовки простое: реши, что именно ты ищешь — ПЕРВЫЙ true (тогда if (P(m)) r = m; else l = m;, ответ r) или ПОСЛЕДНИЙ true (тогда if (P(m)) l = m; else r = m;, ответ l).

Бинарный поиск по вещественным числам

Если ответ — не целое число, а вещественное (например, «найти координату точки с точностью до 10^-6»), останавливаться по правилу «длина интервала стала 1» не получится. Есть два стандартных подхода:

1. Останов по точности. Крутим цикл, пока r - l > ε, где ε — нужная точность (с запасом, скажем 10^-9, если нужна точность 10^-6).
2. Фиксированное число итераций. Крутим цикл ровно, скажем, 100 раз, независимо от текущей разницы r - l. Это чуть менее интуитивно, зато полностью избавляет от проблем с ошибками округления, из-за которых r - l > eps иногда никогда не выполняется (при работе с числами с плавающей точкой такое бывает). Поскольку интервал сужается вдвое за итерацию, ~100 итераций гарантированно доводят интервал до предела точности double (дальше (l + r) / 2 уже не отличается от границ, ведь у double мантисса всего ~52 бита); на практике 50–60 итераций более чем достаточно.

double l = L, r = R;
for (int iter = 0; iter < 100; iter++) {
    double m = (l + r) / 2;
    if (P(m)) r = m;
    else      l = m;
}
// ответ примерно l (или r — они почти совпадают)

Частые технические тонкости

Переполнение при вычислении середины. Классическая формула m = (l + r) / 2 может переполнить тип, если l и r близки к максимуму диапазона int. Безопаснее писать m = l + (r - l) / 2 — математически то же самое, но без промежуточного переполнения.

На каких данных вообще работает бинарный поиск. Стоит помнить, что монотонность обязана быть настоящей, а не «почти всегда» — если предикат хоть иногда «дребезжит» (не монотонен), бинарный поиск может сойтись к неверному ответу, причём без каких-либо явных признаков ошибки: код просто отработает и выдаст неправильное число.

Массив не обязан быть отсортирован буквально — важно лишь то, что интересующий нас предикат монотонен относительно позиции или параметра. А вот для унимодальной функции (с одним экстремумом) обычный бинпоиск сам не находит экстремум — там нужен тернарный поиск, идейно близкий родственник бинарного, но использующий другое сравнение на каждом шаге; с ним познакомимся позже в курсе.

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

В сухом остатке: бинарный поиск — это не «поиск элемента в массиве», а универсальный инструмент нахождения точки перехода монотонного предиката за логарифмическое время. Как только вы увидели в задаче фразу «минимизировать максимум» или «найти наименьшее x, для которого возможно...» — первым делом стоит проверить, не монотонна ли соответствующая функция возможности, и если да — задача, скорее всего, сводится к десятку строк с циклом while (r - l > 1).