Algorithm Guidecomplexity: O(log log n) avg

Interpolation Search

Assumes values are uniformly distributed and estimates the target's position by proportional interpolation. Faster than binary search on uniform data, but it can degrade to O(n) in the worst case on skewed distributions.

01Interpolation Search

Explore How It Works

Starting interpolation search. Assuming the values are evenly spread, a proportion points straight at where the target should be.

Within the span from 5 to 98, 45 lies toward the front. The proportion points at index 3 — closer to the target than the midpoint binary search would pick.

The value there is 34, below 45. The target is to the right, so recompute from just past it.

This time the first value of the remaining range is the target itself, so the proportion lands exactly on it.

The probed slot holds 45 — found in just two comparisons.

Search complete · 45 sits at index 4. Strong on evenly spread data, but degrades to O(n) when the values are skewed.

Live Python

# target: 45

1def interpolation_search(arr, target):

# low: 0

2 low = 0

# high: 9

3 high = len(arr) - 1

4 while low <= high and arr[low] <= target <= arr[high]:

5 if arr[high] == arr[low]:

6 break

7 pos = low + ((target - arr[low]) *

8 (high - low)) // (arr[high] - arr[low])

9 if arr[pos] == target:

10 return pos

11 elif arr[pos] < target:

12 low = pos + 1

13 else:

14 high = pos - 1

15 return -1

1 / 6

02 Understand It Simply

For Everyone

🔑How It Works

Assumes the values are evenly distributed and estimates the target's position proportionally. When the assumption holds it beats binary search.

💡In Plain Words

Assumes an even distribution and estimates the target's position proportionally to skip ahead.

Faster than binary search on uniform data.

📍Where It's Used

–Uniformly distributed sorted data (phone books
–etc.)

03 Python Implementation

A clean, readable reference implementation of the core logic of Interpolation Search.

core_implementation.py

def interpolation_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high and arr[low] <= target <= arr[high]:
        if arr[high] == arr[low]:
            break
        pos = low + ((target - arr[low]) *
                     (high - low)) // (arr[high] - arr[low])
        if arr[pos] == target:
            return pos
        elif arr[pos] < target:
            low = pos + 1
        else:
            high = pos - 1
    return -1