Multiplicative Binary Search

Multiplicative binary search is an advanced algorithmic pattern tailored for unbounded, exponentially scaled, or logarithmically distributed domains. Unlike standard binary search which bisects the linear index space, multiplicative binary search scales the search bounds geometrically using multiplicative factors (such as powers of two or adaptive exponential steps), rendering it optimal for locating unknown upper bounds or navigating monotonic functions across vast dynamical ranges.

double evaluate_predicate(double x) {
    // Example monotonic function: f(x) = x^3 - target
    return (x * x * x) - 125000.0;
}

#include <cmath>
#include <stdexcept>

std::pair<double, double> find_bounds(double initial_guess, double factor, double target) {
    double low = 0.0;
    double high = initial_guess;
    
    // Guard against zero-initialization
    if (high <= 0.0) high = 1.0;
    
    while (evaluate_predicate(high) < 0.0) {
        low = high;
        high *= factor;
        if (std::isinf(high)) {
            throw std::overflow_error("Multiplicative bounds exceeded numeric limits.");
        }
    }
    return {low, high};
}

double multiplicative_binary_search(double tolerance, double factor) {
    auto [low, high] = find_bounds(1.0, factor, 125000.0);
    double mid = low;
    
    while ((high - low) > tolerance * low) {
        // Geometric mean for multiplicative scaling
        mid = std::sqrt(low * high);
        double val = evaluate_predicate(mid);
        
        if (val < 0.0) {
            low = mid;
        } else {
            high = mid;
        }
    }
    return mid;
}

#=['assert abs(multiplicative_binary_search() - 50.0) < 1e-5']

Mathematical Foundations & Asymptotic Analysis

Standard binary search operates in a linear domain space, achieving O(log n) time complexity by halving the interval [low, high] via arithmetic means: mid = (low + high) / 2. Conversely, multiplicative binary search assumes the search space spans multiple orders of magnitude or lacks a predefined upper bound N. The phase consists of two distinct sub-algorithms:
1. Exponential Galloping: Starting from a base step, the algorithm multiplies the probe position by a constant factor c > 1 until the target is bracketed. This takes O(log log n) steps if the target magnitude is known, or bounds an unknown upper limit efficiently.
2. Geometric Bisection: Refinement utilizes the geometric mean mid = sqrt(low * high). This transformation maps exponential growth to linear growth via logarithmic substitution, ensuring uniform relative precision across varying scales.

Engineering Trade-offs & When to Use

Multiplicative binary search is uniquely suited for systems engineering scenarios where data distribution follows a power law, Pareto distribution, or exponential growth curves. Examples include adaptive rate-limiting window sizing, memory allocation tier searches, and financial option pricing models.

However, developers must weigh specific failure modes:
– Floating-Point Underflow/Overflow: Repeated multiplication can rapidly drive values to NaN, infinity, or zero.
– Additive Distributions: If the underlying domain is dense and linear, multiplicative steps incur unnecessary branching overhead compared to traditional binary search.
– Branch Prediction Penalties: Dynamic bounds checks within the galloping phase can disrupt CPU instruction pipelines if not carefully unrolled.

Production Hardening & Edge Case Mitigation

Production deployments must enforce strict invariant checks:
– Step Factor Tuning: Selecting a factor too close to 1.0 (e.g., 1.01) degrades performance toward O(n), while a factor too large (e.g., 10.0) misses optimal bracketing precision.
– Monotonicity Violations: If f(x) contains local non-monotonicity due to floating-point jitter or noisy telemetry, the geometric mean calculation can diverge. Implement robust epsilon comparisons (e.g., std::abs(high – low) <= eps * std::max(1.0, high)).