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

Алгоритм состоит из двух фаз с разными инвариантами. Фаза 1 (поиск границы): начиная с bound = 1, на каждом шаге проверяется a[bound] относительно x; если a[bound] < x, bound удваивается. Как только a[bound] ≥ x (или bound вышел за пределы массива), становится известно: если x вообще есть в массиве, он лежит в диапазоне [bound/2, min(bound, n-1)] — потому что на предыдущем шаге, при bound/2, было доказано a[bound/2] < x. Фаза 2 (уточнение): обычный бинарный поиск (2.2.3.1) внутри этого диапазона.The algorithm has two phases with different invariants. Phase 1 (bound search): starting from bound = 1, at each step a[bound] is checked against x; if a[bound] < x, bound is doubled. Once a[bound] ≥ x (or bound has run past the array), it's known: if x is present in the array at all, it lies in the range [bound/2, min(bound, n-1)] — because at the previous step, at bound/2, a[bound/2] < x was proven. Phase 2 (refinement): plain binary search (2.2.3.1) inside that range.

Ключевое наблюдение по сложности: число шагов фазы 1 — это log₂(p), где p — истинная позиция ответа (или граница массива, если ответа нет), а не log₂(n). Фаза 2 работает над диапазоном размера ~p, что даёт ещё log₂(p) шагов. Итого O(log p) вместо O(log n) — при p ≪ n (ответ находится близко к началу) это строго быстрее обычного бинарного поиска по всему массиву; при p ≈ n асимптотика та же с чуть большей константой.The key complexity observation: phase 1 takes log₂(p) steps, where p is the answer's true position (or the array's bound if there's no answer), not log₂(n). Phase 2 works over a range of size ~p, adding another log₂(p) steps. Total: O(log p) instead of O(log n) — when p ≪ n (the answer sits near the start) this is strictly faster than plain binary search over the whole array; when p ≈ n the asymptotics match with a slightly larger constant.

int exponential_search(const std::vector<int>& a, int x) {
    int n = (int)a.size();
    if (n == 0) return -1;
    if (a[0] == x) return 0;

    int bound = 1;
    while (bound < n && a[bound] < x) bound *= 2; // фаза 1: найти границу// phase 1: find the bound

    int lo = bound / 2, hi = std::min(bound, n - 1);
    while (lo <= hi) {                        // фаза 2: обычный бинарный поиск// phase 2: plain binary search
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == x) return mid;
        else if (a[mid] < x) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Столбики — отсортированный массив; ползунок "позиция x" задаёт, насколько глубоко в массиве лежит искомое значение. Жёлтые столбики отмечают точки удвоения границы (фаза 1), синяя рамка — диапазон бинарного поиска (фаза 2). Обратите внимание, как число шагов фазы 1 растёт с позицией x, а не с размером массива.The bars are a sorted array; the "x position" slider sets how deep into the array the target value sits. Yellow bars mark the doubling points (phase 1), the blue outline is the binary-search range (phase 2). Notice how phase 1's step count grows with x's position, not with the array's size.

Если размер массива n известен и доступ к любому индексу стоит одинаково, обычный бинарный поиск (2.2.3.1) не хуже — экспоненциальный поиск не даёт здесь преимущества, только более сложный код. Выигрыш появляется в двух конкретных случаях: (1) n неизвестно заранее (бесконечный или потоковый источник, где "прочитать элемент" возможно, а "узнать длину" — нет), и тогда обычный бинарный поиск попросту неприменим без этой информации; (2) n известно, но очень велико, а искомый элемент почти наверняка находится близко к началу — тогда O(log p) с p ≪ n ощутимо быстрее O(log n).If array size n is known and accessing any index costs the same, plain binary search (2.2.3.1) is no worse — exponential search gives no advantage here, just more complex code. The win shows up in two specific cases: (1) n is unknown in advance (an infinite or streaming source where "read an element" is possible but "learn the length" isn't), in which case plain binary search simply can't be applied without that information; (2) n is known but very large, and the target is almost certainly near the start — then O(log p) with p ≪ n is noticeably faster than O(log n).