Exponential (Galloping) Search, Rotated Arrays & Ternary Search on Unimodal Functions

1. Exponential (Galloping / Bentley-Yao) Search in $O(\log i)$ Time

Suppose you want to search for a target $x$ in a sorted array of unknown (or enormous) size $N$, where $x$ is known to sit near the beginning (at index $i \ll N$)—such as advancing a posting-list cursor in an inverted search index (Lucene/ripgrep) or TimSort's galloping merge. Standard binary search across $[0, N)$ always pays $\lceil \log_2 N \rceil$ comparisons. Exponential Search (Bentley & Yao, 1976) finds $x$ in $\mathbf{2\lfloor \log_2 i \rfloor + 2 = O(\log i)}$ comparisons:

1. Doubling Phase: Probe indices $b = 1, 2, 4, 8, \dots, 2^k$ until $A[2^k] \ge x$ (or $2^k \ge N$). Since $2^{k-1} \le i \le 2^k$, this takes $\lfloor \log_2 i \rfloor + 1$ comparisons.
2. Binary Search Phase: Run standard binary search inside the bracketed half-open window $(2^{k-1}, \min(2^k, N)]$, which has length $\le 2^{k-1} \le i$ and takes at most $\lfloor \log_2 i \rfloor + 1$ comparisons!

2. Searching Cyclically Rotated Sorted Arrays

When a sorted array of distinct keys $A$ is cyclically rotated (e.g., $[40, 50, 60, 10, 20, 30]$), it splits into an Upper Sorted Prefix (all elements $\ge A[0]$) followed by a Lower Sorted Suffix (all elements $< A[0]$, or $\le A[n-1]$). We can either:

• Find the Minimum Pivot Index in $\log_2 n$ Steps: Apply monotonic binary search with predicate $P(i) := (A[i] \le A[n-1])$, which evaluates to $[F, F, \dots, F, T, T, \dots, T]$ and returns the exact rotation minimum index!
• Single-Pass Direct Rotated Search: At any midpoint $mid$, at least one of the two halves $[lo, mid]$ or $[mid, hi]$ is guaranteed to be strictly sorted! If $A[lo] \le A[mid]$, the left half is sorted (so check if $target \in [A[lo], A[mid])$); otherwise the right half $[mid, hi]$ is sorted (so check if $target \in (A[mid], A[hi]]$).

Production C++20 Implementation: Exponential Search, Rotated Search & Golden-Section Unimodal Optimizer

#include <algorithm>
#include <cmath>
#include <concepts>
#include <cstddef>
#include <numbers>

// 1. Exponential (Galloping) Search from cursor hint: O(log(result - hint)) time & cache-local!
template <std::totally_ordered T>
constexpr std::size_t exponential_lower_bound(const T* a, std::size_t n, const T& target, std::size_t hint = 0) noexcept {
    if (hint >= n || !(a[hint] < target)) {
        // Fallback if target <= a[hint]
        return static_cast<std::size_t>(std::lower_bound(a, a + std::min(hint + 1, n), target) - a);
    }
    std::size_t step = 1;
    std::size_t lo = hint;
    std::size_t hi = hint + 1;
    while (hi < n && a[hi] < target) {
        lo = hi;
        step <<= 1;
        hi = (n - hi > step) ? (hi + step) : n;
    }
    return static_cast<std::size_t>(std::lower_bound(a + lo + 1, a + hi, target) - a);
}

// 2. Discrete Unimodal Peak Finder in log2(n) iterations (1 slope comparison per step)
template <std::totally_ordered T>
constexpr std::size_t find_bitonic_peak(const T* a, std::size_t n) noexcept {
    std::size_t lo = 0, hi = n - 1;
    while (lo < hi) {
        const std::size_t mid = lo + (hi - lo) / 2;
        if (a[mid] < a[mid + 1]) {
            lo = mid + 1; // Rising slope: peak is strictly to the right
        } else {
            hi = mid;     // Falling slope: mid could be the peak
        }
    }
    return lo;
}

// 3. Continuous Golden-Section Search: maximizes unimodal f(x) on [lo, hi] reusing 1 evaluation/step!
template <typename Func>
double golden_section_maximize(Func f, double lo, double hi, int iterations = 70) {
    constexpr double inv_phi  = 1.0 / std::numbers::phi;        // (sqrt(5) - 1) / 2 ≈ 0.618034
    constexpr double inv_phi2 = 1.0 - inv_phi;                  // (3 - sqrt(5)) / 2 ≈ 0.381966

    double m1 = lo + inv_phi2 * (hi - lo);
    double m2 = lo + inv_phi  * (hi - lo);
    double f1 = f(m1);
    double f2 = f(m2);

    for (int it = 0; it < iterations; ++it) {
        if (f1 < f2) {
            lo = m1;
            m1 = m2; f1 = f2; // Reuse previous m2 evaluation!
            m2 = lo + inv_phi * (hi - lo);
            f2 = f(m2);       // Only ONE new f() call per step!
        } else {
            hi = m2;
            m2 = m1; f2 = f1; // Reuse previous m1 evaluation!
            m1 = lo + inv_phi2 * (hi - lo);
            f1 = f(m1);
        }
    }
    return 0.5 * (lo + hi);
}