Exponential Search

Exponential search, also known as galloping search or doubling search, is an algorithmic pattern designed to find the range within which a target value resides in a sorted array, followed by a standard binary search within that bounded range. It operates with exceptional efficiency when the target element is located near the beginning of the data structure, optimizing search bounds via power-of-two index scaling.

template <typename T>
int exponentialSearch(const std::vector<T>& arr, const T& target) {
    if (arr.empty()) return -1;
    if (arr[0] == target) return 0;

    size_t bound = 1;
    while (bound < arr.size() && arr[bound] <= target) {
        bound *= 2;
    }

    size_t lower = bound / 2;
    size_t upper = std::min(bound, arr.size() - 1);
    auto it = std::lower_bound(arr.begin() + lower, arr.begin() + upper + 1, target);
    
    if (it != arr.end() && *it == target) {
        return std::distance(arr.begin(), it);
    }
    return -1;
}

    // Use checked multiplication or safe bit-shifts with explicit cast checks
    size_t max_limit = std::numeric_limits<size_t>::max() / 2;
    while (bound < arr.size() && arr[bound] <= target) {
        if (bound > max_limit) {
            bound = arr.size();
            break;
        }
        bound *= 2;
    }

Mathematical & Algorithmic Analysis

Let n be the total size of the array and i be the 0-based index of the target element. The exponential search algorithm executes in two distinct phases: Phase 1 (Range Finding) and Phase 2 (Binary Search). In Phase 1, the algorithm checks indices 1, 2, 4, 8, …, 2^k until 2^k >= i. This requires roughly log(i) iterations. In Phase 2, a binary search is executed over a sub-array of length at most 2^k = 2 * 2^(k-1) = 2i, consuming O(log(2i)) = O(log i) operations. Consequently, the overall worst-case time complexity is O(log i). When the target is located near the beginning of the collection, exponential search significantly outperforms classical binary search which unconditionally operates in O(log n) time. Space complexity remains O(1) for iterative implementations and O(log i) for recursive stack frames.

Engineering Trade-offs & Unbounded Streams

Unlike standard binary search, which requires upfront knowledge of the array size n, exponential search natively supports unbounded, infinite, or stream-based data structures where the upper bound is initially unknown. By dynamically probing indices via powers of two, the algorithm defers memory boundary discoveries until an overflow or out-of-bounds signal is intercepted from the underlying data provider. However, branching overhead in tight exponential loops can occasionally introduce instruction pipeline stalls compared to unrolled binary search arrays in high-frequency trading or low-latency kernels.