# Interpolation Sequential Search

# 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

```id="is01"
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

```id="is02"
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
```

```id="is03"
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
}
```