Interpolation Search

Interpolation search is an advanced algorithmic pattern designed for searching a key in a sorted array that has been uniformly distributed. Unlike binary search, which inspects the midpoint index uniformly, interpolation search estimates the probable position of the target value by calculating a linear interpolation based on the values at the boundaries of the search space. Under the assumption of uniform distribution, the expected number of probes scales logarithmically with the double logarithm of the input size, yielding sub-logarithmic average-case performance. However, pathological input distributions or clustered data anomalies can severely degrade the search mechanics to linear worst-case complexity.

template <typename T>
requires std::is_arithmetic_v<T>
int validate_and_setup(const std::vector<T>& arr, T target, size_t& low, size_t& high) {
    if (arr.empty()) return -1;
    low = 0;
    high = arr.size() - 1;
    if (target < arr[low] || target > arr[high]) return -1;
    return 0;
}

template <typename T>
size_t compute_probe_position(const std::vector<T>& arr, T target, size_t low, size_t high) {
    if (arr[high] == arr[low]) return low;
    // Using double precision intermediate cast to prevent integer overflow on large ranges
    double numerator = static_cast<double>(target - arr[low]) * static_cast<double>(high - low);
    double denominator = static_cast<double>(arr[high] - arr[low]);
    size_t pos = low + static_cast<size_t>(numerator / denominator);
    if (pos > high) return high;
    if (pos < low) return low;
    return pos;
}

template <typename T>
int interpolation_search_core(const std::vector<T>& arr, T target) {
    size_t low = 0, high = 0;
    if (validate_and_setup(arr, target, low, high) == -1) return -1;

    while (low <= high && target >= arr[low] && target <= arr[high]) {
        if (low == high) {
            if (arr[low] == target) return static_cast<int>(low);
            break;
        }

        size_t pos = compute_probe_position(arr, target, low, high);

        if (arr[pos] == target) {
            return static_cast<int>(pos);
        }
        if (arr[pos] < target) {
            low = pos + 1;
        } else {
            if (pos == 0) break;
            high = pos - 1;
        }
    }
    return -1;
}

#include <cassert>
#include <vector>

void run_interpolation_tests() {
    std::vector<int> uniform_data = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    assert(interpolation_search_core(uniform_data, 40) == 3);
    assert(interpolation_search_core(uniform_data, 10) == 0);
    assert(interpolation_search_core(uniform_data, 100) == 9);
    assert(interpolation_search_core(uniform_data, 25) == -1);
    assert(interpolation_search_core(std::vector<int>{}, 5) == -1);
}

Mathematical Formulation & Complexity Analysis

Interpolation search relies on the assumption that the underlying data points follow a linear cumulative distribution function (CDF). Given a sorted interval [arr[low], arr[high]], the estimated position index pos is derived from the linear equation of a line passing through (low, arr[low]) and (high, arr[high]):

pos = low + ((target – arr[low]) * (high – low)) / (arr[high] – arr[low])

Under strict uniform distribution assumptions, the size of the search space shrinks exponentially relative to its previous size, raising the recursion depth relation to log log n. Thus, the average-case time complexity is O(log log n).

However, if the data is exponentially clustered (e.g., values grow exponentially like powers of 2), the denominator grows drastically while the numerator remains small, leading to excessive probe steps that yield a worst-case time complexity of O(n). Space complexity remains strictly O(1) when implemented iteratively, as no auxiliary call stack or memory allocations are required.

Production Hardening & Fallback Strategies

In production systems, deploying pure interpolation search carries architectural risk due to its vulnerability against adversarial or highly skewed inputs. To mitigate O(n) degradation, robust systems employ hybrid architectures known as 'Interpolation-Binary Search' or 'Galloping Search'. If the probe step variance or iteration count exceeds a predefined threshold (such as 2 * log2(n)), the algorithm immediately falls back to standard binary search guarantees of O(log n). Furthermore, strict integer and floating-point overflow protections must be wrapped around subtraction and multiplication blocks when indexing enterprise-scale datasets containing billions of records.