# Interpolation Search with Fallback

# Interpolation Search with Fallback

Interpolation search with fallback combines the speed of interpolation search on well distributed numeric keys with the reliability of binary search. It estimates where the target should be by value, but falls back to ordinary binary search when the estimate becomes poor, unstable, or unsafe.

This gives good performance on near uniform data while preserving the worst case behavior of binary search.

## Problem

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

$$
A[i] = x
$$

If no such index exists, return $-1$.

## Idea

Interpolation search estimates the position using the relative value of $x$ between the left and right endpoints.

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

This estimate works well when values are close to uniformly distributed. When values are skewed, clustered, or duplicated, interpolation can make little progress. A fallback prevents degeneration.

## Algorithm

```text id="isf01"
interpolation_search_with_fallback(A, x):
    l = 0
    r = length(A) - 1
    bad_steps = 0

    while l <= r and A[l] <= 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 pos < l or pos > r:
            break

        if A[pos] == x:
            return pos

        old_l = l
        old_r = r

        if A[pos] < x:
            l = pos + 1
        else:
            r = pos - 1

        if r - l > (old_r - old_l) * 3 // 4:
            bad_steps = bad_steps + 1
        else:
            bad_steps = 0

        if bad_steps >= 2:
            break

    return binary_search(A, x, l, r)
```

## Example

Let

$$
A = [1, 2, 3, 4, 1000, 1001, 1002, 1003]
$$

and

$$
x = 1002
$$

The values are highly nonuniform. Interpolation may estimate a position too far to the right or make weak progress. After several poor steps, the algorithm falls back to binary search over the remaining interval.

| phase          | action                         |
| -------------- | ------------------------------ |
| interpolation  | estimate likely position       |
| progress check | detect weak interval shrinkage |
| fallback       | finish with binary search      |

## Correctness

The interpolation phase only discards elements after comparing against an actual array value. If $A[pos] < x$, all positions at or before `pos` are too small, so the left boundary can move to `pos + 1`. If $A[pos] > x$, all positions at or after `pos` are too large, so the right boundary can move to `pos - 1`.

When interpolation stops, the target, if present, remains inside the current interval. Binary search is correct on sorted intervals, so the fallback returns the correct index or reports failure.

## Complexity

| case                    | time             |
| ----------------------- | ---------------- |
| best                    | $O(1)$           |
| average on uniform data | $O(\log \log n)$ |
| fallback worst case     | $O(\log n)$      |

Space:

$$
O(1)
$$

The fallback improves the worst case over plain interpolation search, which can degrade to $O(n)$ on adversarial distributions.

## When to Use

Use interpolation search with fallback when:

* keys are numeric
* data is sorted
* values are often close to uniformly distributed
* worst case reliability matters
* query performance should remain stable under skew

It is useful for timestamp ranges, numeric IDs, ordered logs, and database pages where distributions are usually regular but not guaranteed.

## Implementation

```python id="isf02"
def binary_search_range(a, x, left, right):
    while left <= right:
        mid = (left + right) // 2
        if a[mid] == x:
            return mid
        if a[mid] < x:
            left = mid + 1
        else:
            right = mid - 1
    return -1

def interpolation_search_with_fallback(a, x):
    left, right = 0, len(a) - 1
    bad_steps = 0

    while left <= right and a[left] <= x <= a[right]:
        if a[left] == a[right]:
            return left if a[left] == x else -1

        old_left, old_right = left, right
        pos = left + (x - a[left]) * (right - left) // (a[right] - a[left])

        if pos < left or pos > right:
            break

        if a[pos] == x:
            return pos

        if a[pos] < x:
            left = pos + 1
        else:
            right = pos - 1

        old_width = old_right - old_left
        new_width = right - left

        if old_width > 0 and new_width > old_width * 3 // 4:
            bad_steps += 1
        else:
            bad_steps = 0

        if bad_steps >= 2:
            break

    return binary_search_range(a, x, left, right)
```

```go id="isf03"
func binarySearchRange(a []int, x int, left int, right int) int {
    for left <= right {
        mid := (left + right) / 2
        if a[mid] == x {
            return mid
        }
        if a[mid] < x {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return -1
}

func InterpolationSearchWithFallback(a []int, x int) int {
    left, right := 0, len(a)-1
    badSteps := 0

    for left <= right && a[left] <= x && x <= a[right] {
        if a[left] == a[right] {
            if a[left] == x {
                return left
            }
            return -1
        }

        oldLeft, oldRight := left, right
        pos := left + (x-a[left])*(right-left)/(a[right]-a[left])

        if pos < left || pos > right {
            break
        }

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

        if a[pos] < x {
            left = pos + 1
        } else {
            right = pos - 1
        }

        oldWidth := oldRight - oldLeft
        newWidth := right - left

        if oldWidth > 0 && newWidth > oldWidth*3/4 {
            badSteps++
        } else {
            badSteps = 0
        }

        if badSteps >= 2 {
            break
        }
    }

    return binarySearchRange(a, x, left, right)
}
```