Interpolation Search

#How does it work?

Interpolation search narrows the range like binary search, but instead of the middle it looks where the value should be, like opening a phone book near the end when looking for "Wilson".

The position is estimated by proportion from the values at both ends of the range: if the target is x% of the way between them by value, we look about x% of the way along by position.

With evenly spread values it can find the target in a single probe. With very skewed data (say 1, 2, 3, 1000000) the guesses get poor and it can slow down to linear search.

#Live animation

lo = 0; hi = n - 1
while lo <= hi and a[lo] <= target <= a[hi]:
  pos = lo + (target - a[lo]) · (hi - lo) / (a[hi] - a[lo])
  if a[pos] == target: return pos
  if a[pos] < target: lo = pos + 1 else: hi = pos - 1
return -1

#Step by step

1. 01Take the whole array as the range with lo and hi.
2. 02If the target isn't between a[lo] and a[hi], stop: it isn't there.
3. 03Estimate the position: pos = lo + (target − a[lo]) · (hi − lo) / (a[hi] − a[lo]).
4. 04If a[pos] is the target, done; if smaller set lo = pos + 1, if larger set hi = pos − 1.
5. 05Repeat until the range is empty.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

def interpolation_search(a: list[int], target: int) -> int:
    """a must be sorted. Guesses the position from the values instead of taking the middle."""
    lo, hi = 0, len(a) - 1
    while lo <= hi and a[lo] <= target <= a[hi]:
        if a[hi] == a[lo]:
            pos = lo
        else:
            pos = lo + (target - a[lo]) * (hi - lo) // (a[hi] - a[lo])
        if a[pos] == target:
            return pos
        if a[pos] < target:
            lo = pos + 1
        else:
            hi = pos - 1
    return -1


numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(interpolation_search(numbers, 13))
print(interpolation_search(numbers, 4))

#Complexity

With uniformly distributed values the average is O(log log n) probes: 4–5 for a million elements. In the worst case (very skewed data) each probe removes just one element and time grows to O(n). There is no O(log n) guarantee as with binary search.

#When to use it?

Faster than binary search on large, sorted, roughly evenly spread data (sequential ids, timestamps, evenly spaced measurements). If the distribution is unknown or skewed, binary search is the safer choice.

#Practice

Log in to answer questions and save your progress.