Interpolation Search — 40x Slowdown on Skewed Data

Interpolation search achieves O(log log n) on uniformly distributed data — compared to binary search's O(log n). For n=10^9 uniformly distributed integers, that is ~5 probes versus ~30 probes. For the right data, that is a 6x speedup in comparison count.

The catch: 'uniformly distributed' is rarely guaranteed in real data. Database query optimisers use similar interpolation logic — estimating where a value falls in a range based on column statistics and histograms. That is interpolation search applied to index structures. Understanding interpolation search means understanding how query planners estimate probe costs.

The Interpolation Formula

Instead of mid = (lo + hi) // 2, interpolation search estimates: pos = lo + ((target - arr[lo]) × (hi - lo)) / (arr[hi] - arr[lo])

This is linear interpolation — projecting where the target would fall if values were uniformly distributed between arr[lo] and arr[hi].

def interpolation_search(arr: list, target) -> int:
    lo, hi = 0, len(arr) - 1
    while lo <= hi and arr[lo] <= target <= arr[hi]:
        if lo == hi:
            return lo if arr[lo] == target else -1
        # Interpolation probe
        pos = lo + int((target - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]))
        if arr[pos] == target:
            return pos
        elif arr[pos] < target:
            lo = pos + 1
        else:
            hi = pos - 1
    return -1

# Uniformly distributed data — very fast
arr = list(range(0, 1000, 10))  # [0, 10, 20, ..., 990]
print(interpolation_search(arr, 680))  # 68
print(interpolation_search(arr, 777))  # -1 (not a multiple of 10)

C++ and Python Implementations

The previous section showed the Python implementation. Here is the equivalent C++ version for those working in systems-level contexts like trading engines or game servers. C++ requires careful handling of integer types to avoid overflow. The logic mirrors the Python version exactly.

#include <iostream>
#include <vector>
#include <cstdint>

int interpolation_search(const std::vector<int>& arr, int target) {
    int lo = 0, hi = arr.size() - 1;
    while (lo <= hi && arr[lo] <= target && target <= arr[hi]) {
        if (lo == hi) {
            return (arr[lo] == target) ? lo : -1;
        }
        // Use 64-bit arithmetic to avoid overflow
        int64_t numerator = static_cast<int64_t>(target - arr[lo]) * (hi - lo);
        int64_t denominator = arr[hi] - arr[lo];
        int pos = lo + static_cast<int>(numerator / denominator);
        if (arr[pos] == target) return pos;
        else if (arr[pos] < target) lo = pos + 1;
        else hi = pos - 1;
    }
    return -1;
}

int main() {
    std::vector<int> arr = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    std::cout << interpolation_search(arr, 60) << std::endl;  // 6
    std::cout << interpolation_search(arr, 55) << std::endl;  // -1
    return 0;
}

When It Excels vs When It Fails

Excels: Uniformly distributed sorted arrays — phone books, sorted numeric IDs, timestamps at regular intervals. O(log log n) expected.

Fails badly: Non-uniform distributions — geometric sequences, or data clustered at one end. Worst case O(n). Example: arr = [1, 2, 4, 8, 16, ..., 2^n] — interpolation probes near the start every time for large targets.

Rule of thumb: Use interpolation when you know the data is roughly uniform. Use binary search otherwise.

Advantages and Disadvantages

The table below contrasts interpolation search's behaviour on uniform versus non‑uniform distributions:

Complexity Analysis

Average (uniform data): O(log log n) — the probe reduces search space multiplicatively Worst case: O(n) — non-uniform distribution can make it probe one element at a time Space: O(1)

For n=10^9 uniform elements: log log n ≈ 5 probes vs binary search's log n ≈ 30 probes.

O(log log n) vs O(n) Boundary Cases

The following table lists explicit boundary conditions that determine whether interpolation search performs in O(log log n) or degrades to O(n). Understanding these helps you write guards in production.

Real-World Application: Database Query Planning

Database systems like PostgreSQL and MySQL use histogram statistics to estimate where a value falls within an index range. For example, a B-tree range scan estimates the number of pages to traverse based on column value distribution — that's interpolation search on index pages.

Query planners maintain histogram buckets (e.g., 100 equal-height buckets). For a WHERE clause like age = 35, the planner does: estimate position = bucket_start + ((35 - bucket_min) * bucket_width / (bucket_max - bucket_min)). Sound familiar? It's exactly the interpolation formula.

If the histogram shows uniform distribution, the planner assumes few pages to scan. If skewed, it may choose a full index scan instead.

Comparison with Binary Search: When to Choose Which

For most production systems, binary search is the safer default. Use interpolation search only when: - Data is proven to be near-uniform (e.g., auto-increment IDs with no gaps) - The search array is in DRAM (not disk) — random probe positions kill HDD/SSD seek costs - Worst-case O(n) is acceptable or mitigated by fallback

Recursive Implementation in Java

For completeness, here is a recursive variant of interpolation search in Java. Recursion avoids the explicit while loop but adds stack overhead. In practice, the iterative approach is preferred for performance and to avoid stack overflow on large inputs.

public class InterpolationSearchRecursive {
    public static int search(int[] arr, int target, int lo, int hi) {
        if (lo > hi || arr[lo] > target || arr[hi] < target) {
            return -1;
        }
        if (lo == hi) {
            return (arr[lo] == target) ? lo : -1;
        }
        // Avoid division by zero
        if (arr[hi] == arr[lo]) {
            return (arr[lo] == target) ? lo : -1;
        }
        int pos = lo + (int)(((long)(target - arr[lo]) * (hi - lo)) / (arr[hi] - arr[lo]));
        if (arr[pos] == target) {
            return pos;
        } else if (arr[pos] < target) {
            return search(arr, target, pos + 1, hi);
        } else {
            return search(arr, target, lo, pos - 1);
        }
    }

    public static void main(String[] args) {
        int[] arr = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
        System.out.println(search(arr, 60, 0, arr.length - 1));  // 6
        System.out.println(search(arr, 55, 0, arr.length - 1));  // -1
    }
}

Frequently Asked Questions