How Interpolation Search Works

Back to the phone book one more time. Looking for "Zeller"? You don't open to the middle page — you flip almost straight to the back, because you know names starting with Z live near the end. You're not guessing blindly; you're using the actual value you're looking for to estimate its position. That's exactly what Interpolation Search does to sorted numeric data, and when the data is evenly spread out, it's dramatically faster than Binary Search's "always check the middle" approach.

How Interpolation Search Works

Instead of always checking the middle element like Binary Search, Interpolation Search calculates a smarter guess using a formula based on the target's value relative to the values at both ends of the current range:

pos = low + ((target - arr[low]) × (high - low)) / (arr[high] - arr[low])

This formula essentially says: "if the target is close in value to arr[high], guess a position near the high end. If it's close to arr[low], guess near the low end." It's the same intuition as flipping straight to the back of the phone book for "Zeller."

Walking Through an Example

Search for 70 in the evenly-spaced sorted array [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]:

• low = 0 (value 10), high = 9 (value 100)
• pos = 0 + ((70 − 10) × (9 − 0)) / (100 − 10) = 0 + (60 × 9) / 90 = 6
• Check index 6: 70 → match, found immediately

One calculation, one comparison. Binary Search would have needed to check the middle (index 4, value 50) first, then narrow down from there — more steps, because it doesn't use the actual values to make its guess.

Java Implementation

public class InterpolationSearch {
    public static int interpolationSearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high && target >= arr[low] && target <= arr[high]) {
            if (low == high) {
                return (arr[low] == target) ? low : -1;
            }

            // Estimate the position based on the target's value
            int pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]);

            if (arr[pos] == target) {
                return pos; // found it
            } else if (arr[pos] < target) {
                low = pos + 1; // target is further right
            } else {
                high = pos - 1; // target is further left
            }
        }
        return -1; // not found
    }

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

⚠️ Warning

This only works well on uniformly distributed sorted data — values spread out fairly evenly, like [10, 20, 30, 40...]. On unevenly distributed data like [1, 2, 3, 1000000], the formula's guesses get thrown off badly, and performance can degrade all the way to O(n).

Time Complexity

📝 Complexity Breakdown

Best case: O(1)
Average case: O(log log n) — on uniformly distributed data, remarkably fast
Worst case: O(n) — on poorly distributed data, no better than Linear Search
Space: O(1)

O(log log n) is genuinely hard to intuit — for a billion elements, log log n is roughly 5. That's the payoff of using the data's actual values instead of just its size. But that payoff is conditional: it only shows up when the data is spread out evenly, which is why this isn't a universal replacement for Binary Search, just a specialized tool for the right situation.

Common Interview Questions

• Why does Interpolation Search require uniformly distributed data to perform well?
• What happens to its performance on data like [1, 2, 3, 4, 1000000], and why?
• How does the interpolation formula relate to how you'd naturally search a phone book or dictionary?

The Takeaway

Interpolation Search is a reminder that "know your data" can be an algorithm design principle, not just a performance tip — using actual values instead of just positions unlocked a faster average case, at the cost of a worse worst case if that assumption breaks. Next up: Exponential Search, which solves a completely different problem — searching efficiently when you don't even know how large the array is.

➡️ Next in the Series

Exponential Search: Searching When You Don't Know the Size

Happy learning!
— Team CodeElevateX 🚀