TUTORIAL · Algorithm

Interpolation Search

This tutorial introduces the Interpolation Search Algorithm.

On this page

Interpolation search estimates where a target belongs by comparing its value with the values at the ends of the current range. On sorted data with values distributed fairly evenly, this value-based probe can reach a target in fewer probes than binary search, which always checks the midpoint. The estimate is less useful when values are clustered or unevenly spaced, so the distribution assumption matters. The dictionary analogy is useful: a reader looking for a word beginning with “s” opens nearer the back than the middle, then narrows the pages based on what they see.

Interpolation Search Algorithm

For an ascending array A and target X, keep inclusive bounds lo and hi, initially the first and last indices. The array must be sorted; otherwise the range comparisons and probe estimate cannot safely discard values. While X lies between A[lo] and A[hi], estimate a position with:

mid = lo + (X - A[lo]) * (hi - lo) / (A[hi] - A[lo])

The calculation uses integer division, so the estimate is an array index. If A[mid] is less than X, continue at mid + 1; if it is greater, continue at mid - 1; if it matches, return mid. Before estimating, handle equal endpoint values: if they match X, return an endpoint; otherwise the target cannot occur in that range. Stop when the bounds cross. A target outside the current endpoint values can also be rejected immediately. These checks prevent division by zero and avoid indexing an empty range.

Interpolation Search Example

Consider A = (1, 3, 7, 8, 11, 15, 17, 18, 21) and target X = 18. Initially lo = 0, hi = 8, A[lo] = 1, and A[hi] = 21. The estimate is 0 + (18 - 1) * (8 - 0) / (21 - 1) = 6 after integer division. Since A[6] = 17 is less than the target, set lo = 7. The next estimate is 7 + (18 - 18) * (8 - 7) / (21 - 18) = 7. Now A[7] = 18, so the search returns index 7.

Interpolation Search Algorithm Implementation

This complete C++ example uses the same values and target as the trace. The function returns a zero-based index when it finds the target and -1 otherwise.

Run this example:

#include <iostream>
#include <limits>
#include <vector>

static_assert(std::numeric_limits<int>::digits <= 31,
              "This implementation supports int types up to 32 bits");

int interpolationSearch(const std::vector<int>& values, int target) {
    if (values.empty() ||
        values.size() > static_cast<std::size_t>(std::numeric_limits<int>::max())) {
        return -1;
    }

    int lo = 0;
    int hi = static_cast<int>(values.size()) - 1;
    while (lo <= hi && target >= values[lo] && target <= values[hi]) {
        if (values[lo] == values[hi]) {
            return values[lo] == target ? lo : -1;
        }

        const int mid = lo + static_cast<int>(
            ((static_cast<long long>(target) - static_cast<long long>(values[lo])) *
             (hi - lo)) /
            (static_cast<long long>(values[hi]) -
             static_cast<long long>(values[lo])));

        if (values[mid] == target) return mid;
        if (values[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

int main() {
    const std::vector<int> values{1, 3, 7, 8, 11, 15, 17, 18, 21};
    const int target = 18;
    const int result = interpolationSearch(values, target);
    if (result >= 0) std::cout << "Element found at index " << result << '\n';
    else std::cout << "Element not found\n";
}
Element found at index 7

The guards cover a zero-element vector, a target outside the current value range, and a range whose endpoint values are equal. This implementation requires int to have at most 32 bits and supports vectors with at most INT_MAX elements; it checks the size before converting an index to int. Casting both values to long long before each subtraction keeps the numerator difference and denominator safe for the full 32-bit int range. The largest possible numerator product is (2^32 - 1) * (INT_MAX - 1), which fits in a signed 64-bit long long; the quotient is between zero and hi - lo, so adding it to lo stays within the bounds. The input must still be sorted in ascending order. The example is self-contained and does not require additional files.

Interpolation Search Algorithm Complexity

Time Complexity

The best case is O(1): the first estimated position contains the target. With values distributed roughly uniformly across the sorted range, the average time is O(log log n), because each value-based estimate tends to leave a much smaller interval. This average-case result depends on that distribution assumption; it is not a guarantee for every sorted array.

The worst case is O(n). If value estimates repeatedly make little progress, the algorithm may inspect a linear number of positions. This can happen with highly uneven distributions, so binary search may be a more predictable choice when the distribution is unknown or irregular.

Space Complexity

The iterative implementation uses a fixed number of scalar variables, so its auxiliary space is O(1). It does not allocate another array or recurse.