Interpolation Search is what humans actually do when they open a dictionary. For a word starting with T, you open near the back; for A, near the front.

Instead of always probing the midpoint, it estimates where the target should be based on its value relative to the range’s min and max. On uniformly distributed data, it reaches an astonishing O(log log n) average case.

How It Works

1. Start with the range [low, high].
2. Estimate the target’s position with the probe formula:

   probe = low + ((high - low) / (arr[high] - arr[low])) * (target - arr[low])

3. If arr[probe] == target, return probe.
4. If target < arr[probe], search left; otherwise search right.
5. Repeat until found or the range is exhausted.

Key Insight

The formula is just linear interpolation: it assumes values are spread evenly, so the target’s fraction of the value range equals its fraction of the index range.

• If arr = [0, 10, 20, …, 1000] and you want 980, the probe lands near the last index immediately — one step instead of ~7.
• That is the O(log log n) promise: each probe narrows the range dramatically on uniform data.

The assumption is fragile. If the data is skewed (values cluster), the estimate is wrong and the search can degenerate to a near-linear scan.

Worked Example

Search for 80 in the uniform array [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]:

• [low=0, high=9]: probe = 0 + (9/90) * 70 = 7 → arr[7]=80 → return 7 (one probe!)

Search for 35:

• [0, 9]: probe = 0 + (9/90) * 25 = 2 → arr[2]=30 < 35 → search right
• [3, 9]: probe = 3 + (6/70) * 5 ≈ 3 → arr[3]=40 > 35 → search left → range empty → return -1

In the visualizer, the probe marker jumps toward the value’s estimated location rather than always landing mid-range.

Edge Cases & Pitfalls

• arr[high] == arr[low] — the denominator goes to zero (division by zero). Guard by returning -1 or falling back to a linear scan for that range.
• Target outside [arr[low], arr[high]] — the loop condition target >= arr[low] and target <= arr[high] prevents probing outside. Keep it, or you risk infinite loops.
• Skewed data — worst case is O(n). For non-uniform distributions, plain binary search is safer and still O(log n).
• Duplicates — returns some matching index. The probe formula assumes distinct values and can behave erratically with heavy duplication.

Comparison With Other Searches

Applications

• Large uniformly distributed sorted datasets (IDs, timestamps, measurement series)
• Dictionary-style lookups where the key distribution is known to be even
• Hybrid searches that fall back to binary search when estimates degrade

Practice Trajectory

1. Compute the probe position for target 50 in [10, 20, 30, 40, 50] by hand.
2. Explain the division-by-zero risk when all values in the range are equal.
3. Construct a skewed array where the first probe is far from the target, and trace the degradation.
4. Argue why the average case is O(log log n) on uniform data.
5. Implement interpolation search with the target-in-range guard, then add a binary-search fallback.