Экспоненциальный поиск

Бинарный поиск требует двух границ. В части задач правой границы просто нет — или она есть, но такая огромная, что подставлять её жалко.

Примеры:

• поток данных неизвестной длины, доступ по индексу есть, а размер узнать нельзя;
• ответ — целое число, про которое известно только, что оно неотрицательно;
• вычисление функции дорогое, и лишние двадцать шагов по «бесконечности» стоят заметно.

Решение — сначала найти границу удвоением, потом бинарить.

Схема

// первый индекс, где a[i] >= x
int search(const vector<int>& a, int x) {
    int n = a.size();
    if (n == 0 || a[0] >= x) return 0;

    int bound = 1;
    while (bound < n && a[bound] < x) bound *= 2;   // разгон

    int l = bound / 2, r = min(bound, n);           // a[l] < x, справа граница
    while (r - l > 1) {
        int m = l + (r - l) / 2;
        if (a[m] < x) l = m; else r = m;
    }
    return r;
}

Разгон делает $\lceil \log_2 p \rceil$ шагов, где $p$ — позиция ответа. После него известно, что ответ лежит между bound/2 и bound, а это отрезок длины bound/2 — ещё столько же шагов бинарного поиска.

Итого $O(\log p)$ вместо $O(\log n)$. Логарифм от ответа, а не от размера данных — вот в чём выигрыш. Если ответ близок к началу, экспоненциальный поиск заметно быстрее обычного.

Границы: где ломается

Условие цикла разгона — bound < n && a[bound] < x. Порядок важен: поменяете местами — прочитаете a[bound] за границей массива.

Если размер неизвестен вовсе (интерактивная задача, поток), проверка на выход за границу заменяется на ответ судьи вида «такого индекса нет», и он трактуется как «значение бесконечно велико».

И следите за переполнением: bound *= 2 при bound около $2^{30}$ выкидывает int в минус. Для больших диапазонов — long long.

Поиск по битам

Есть другой способ написать бинарный поиск, который иногда удобнее: собирать ответ по одному биту, от старшего к младшему.

// наибольшее k, при котором check(k) истинно; известно, что k < 2^LOG
long long k = 0;
for (int bit = LOG - 1; bit >= 0; bit--)
    if (check(k + (1LL << bit))) k += 1LL << bit;

Тот же логарифм, но без переменных l и r — и, что важнее, без единого шанса перепутать, куда сдвигать границу. Многим этот вариант кажется надёжнее классического.

У него есть и практическое преимущество: ответ строится монотонно возрастая, и если check умеет достраиваться от предыдущего значения (например, это проход по дереву или накопление суммы), то пересчёт с нуля не нужен. На этом стоят двоичные подъёмы в деревьях и поиск $k$-го элемента в дереве Фенвика.

Поиск в неограниченном пространстве ответа

Тот же приём в задачах на поиск по ответу, где верхняя граница неочевидна:

long long hi = 1;
while (!check(hi)) hi *= 2;      // нашли заведомо истинную границу
long long lo = hi / 2;           // и заведомо ложную
while (hi - lo > 1) {
    long long mid = lo + (hi - lo) / 2;
    if (check(mid)) hi = mid; else lo = mid;
}

Это честнее, чем подставлять «бесконечность» наугад. Слишком маленькая константа даёт неверный ответ, слишком большая — переполнение внутри check или лишние итерации. Удвоение снимает вопрос целиком.

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

Когда это не нужно

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

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