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

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

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)

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)
}