Interpolation Search

Searching O(log log n) O(1)

Estimates the probe position from the target's value relative to the window's endpoints — near O(log log n) on uniformly spread data.

Idle

Searching a sorted array of 8 for 15.

InvariantThe target, if present, lies in [0..7]. The probe guesses where by assuming values spread evenly.

1/5

comparisons0probes0lo0hi7pos0

checkingfoundeliminated

interpolation-search.c

int interpolationSearch(int arr[], int n, int target) {
    int lo = 0, hi = n - 1;
    while (lo <= hi && target >= arr[lo] && target <= arr[hi]) {
        if (lo == hi) {
            if (arr[lo] == target) return lo;
            return -1;
        }
        if (arr[hi] == arr[lo])   /* flat window: all equal */
            return lo;            /* loop guard => match    */
        int pos = lo + (target - arr[lo]) * (hi - lo)
                       / (arr[hi] - arr[lo]);
        if (arr[pos] == target)
            return pos;
        if (arr[pos] < target)
            lo = pos + 1;
        else
            hi = pos - 1;
    }
    return -1;
}

How Interpolation Search works

Instead of the middle, probe where the target should be proportionally: if it's 90% of the way between the window's end values, probe 90% of the way in. Like opening a dictionary near the right letter.

Best case

Uniformly distributed keys: O(log log n) probes.

Worst case

Skewed distributions (e.g. exponential): degenerates to O(n).

When to use it

Large sorted arrays whose keys are close to uniformly distributed.