Interpolation Sequential Search

Interpolation sequential search combines estimation and local scanning. It first predicts where the target should lie using interpolation, then performs a short sequential search around that estimate.

This method is effective when values are approximately uniformly distributed and when exact positioning may be noisy or approximate.

Problem

Given a sorted array $A$ and a target $x$ , find an index $i$ such that

A[i] = x

or report failure.

Idea

Instead of starting from the beginning or halving the range, estimate the position using value distribution:

pos = l + \frac{(x - A[l])(r - l)}{A[r] - A[l]}

This estimate gives a likely index. Then perform a small linear scan near that position to find the exact match.

Algorithm

interpolation_sequential_search(A, x):
    l = 0
    r = length(A) - 1

    while l <= r and A[l] <= x <= A[r]:
        if A[l] == A[r]:
            if A[l] == x:
                return l
            else:
                return -1

        pos = l + (x - A[l]) * (r - l) // (A[r] - A[l])

        if A[pos] == x:
            return pos

        # local scan around pos
        i = pos - 1
        while i >= l and A[i] >= x:
            if A[i] == x:
                return i
            i -= 1

        i = pos + 1
        while i <= r and A[i] <= x:
            if A[i] == x:
                return i
            i += 1

        return -1

    return -1

Example

Let

A = [10, 20, 30, 40, 50, 60, 70]

and

x = 42

Interpolation estimates:

pos \approx 3

Check $A[3] = 40$ , then scan locally:

step	index	value	action
1	3	40	check
2	4	50	stop (exceeds)

Target not found.

Correctness

The interpolation step narrows the search to a likely region based on value distribution. The local scan ensures that even if the estimate is slightly off, all nearby candidates are checked. The bounds prevent scanning outside the valid region.

Complexity

case	time
best	$O(1)$
average (uniform data)	$O(\log \log n)$
worst	$O(n)$

Space:

O(1)

When to Use

Use this method when:

the data is sorted and roughly uniform
interpolation gives good estimates
small local scans are cheaper than full binary search steps

It is suitable for numeric datasets with predictable spacing, such as timestamps or evenly distributed keys.

Implementation

def interpolation_sequential_search(a, x):
    l, r = 0, len(a) - 1

    while l <= r and a[l] <= x <= a[r]:
        if a[l] == a[r]:
            return l if a[l] == x else -1

        pos = l + (x - a[l]) * (r - l) // (a[r] - a[l])

        if a[pos] == x:
            return pos

        i = pos - 1
        while i >= l and a[i] >= x:
            if a[i] == x:
                return i
            i -= 1

        i = pos + 1
        while i <= r and a[i] <= x:
            if a[i] == x:
                return i
            i += 1

        return -1

    return -1

func InterpolationSequentialSearch(a []int, x int) int {
    l, r := 0, len(a)-1

    for l <= r && a[l] <= x && x <= a[r] {
        if a[l] == a[r] {
            if a[l] == x {
                return l
            }
            return -1
        }

        pos := l + (x-a[l])*(r-l)/(a[r]-a[l])

        if a[pos] == x {
            return pos
        }

        for i := pos - 1; i >= l && a[i] >= x; i-- {
            if a[i] == x {
                return i
            }
        }

        for i := pos + 1; i <= r && a[i] <= x; i++ {
            if a[i] == x {
                return i
            }
        }

        return -1
    }

    return -1
}