Does interpolation search work on unsorted data?

The standard algorithm requires sorted keys; its interval elimination depends on that order.

Is it always faster than binary search?

No. Distribution, arithmetic overhead and storage behavior matter, and unfavorable inputs can make it much slower.

What if both endpoint values are equal?

Avoid the division. In a sorted interval, every value then equals that endpoint, so the target either matches it or is absent from the interval.

AI Glossary / Graphs and symbolic AI / Intermediate

Interpolation search

Definition

Interpolation search is a search algorithm for a sorted sequence of numerical keys. It estimates where a target is likely to occur from its value relative to the current endpoint values, probes that position and narrows the search interval according to the comparison.

What it means

Binary search chooses the middle position regardless of the target's value. Interpolation search uses the values themselves: a target close to the low endpoint suggests a position near the beginning of the remaining interval.

The estimate is most useful when numerical distance gives a reasonable indication of position. A long gap or heavily clustered values can make the prediction poor even though the array is correctly sorted.

This is an exact lookup procedure, not a method for inventing a missing value between measurements. The estimated position tells the algorithm where to inspect; equality with the stored key still determines whether the target has been found.

How it works

For ascending array A with candidate indices low through high, a common probe is low + floor((target − A[low]) × (high − low)/(A[high] − A[low])). This maps the target's fraction of the value interval onto the index interval.

If the probed key equals the target, return its position. If it is smaller, continue above that position; if larger, continue below it. Stop when no candidate remains or when the target lies outside the remaining endpoint values.

Implementations must handle an empty interval and equal endpoint values before dividing. They also need safe arithmetic and guaranteed progress after a failed comparison. Duplicate keys require a clear return policy: finding one occurrence does not by itself find the first or last. Correct comparisons protect correctness even when the position estimate is inaccurate.

Three practical examples

An algorithm exercise locates a number in a sorted array whose values are approximately spread across a range.
A data-platform experiment compares lookup behavior on evenly spread identifiers and heavily clustered identifiers.
A performance review checks whether value-based position estimates remain useful after the distribution of stored keys changes.

Think of it this way

Think of searching a numbered directory by opening near where the desired number seems likely to fall. A low number suggests an early page and a high number suggests a later page.

This analogy relies on number ranges roughly matching page positions. If most records occupy a small numerical range and a few have enormous values, that intuition can be misleading. The algorithm must still inspect and compare actual entries.

Worked example

Tracing a search and a misleading estimate

Consider the sorted array [10, 20, 30, 40, 50, 60, 70, 80], indexed from 0 to 7. To find 60, the initial estimate is 0 + floor((60 − 10) × 7/(80 − 10)) = floor(350/70) = 5. The value at index 5 is 60, so the search succeeds at that probe.

For missing target 65, the first probe is floor(55 × 7/70) = 5. Because 60 is smaller than 65, the remaining interval begins at index 6, whose value is 70. The target is now below the interval's smallest key, so it is absent. No approximate match should be reported as an exact result.

Now change the data to [1, 2, 3, 4, 5, 6, 7, 1000] and search for 7. The initial estimate is floor(6 × 7/999) = 0, far from the target at index 6. With the same formula and upper endpoint, subsequent estimates can advance only one position at a time.

This contrast shows why sorted order alone does not ensure fast interpolation search. The first example illustrates a favorable layout, not a universal one-probe guarantee.

Illustrative case study

The fictional Maple Lookup team tests a numerical lookup routine on one tidy demonstration dataset. Before selecting it, reviewers add missing targets, duplicate keys, a constant-valued array and a dataset with a large outlier.

They record both successful results and the number of probes. The outlier case explains why an algorithm that looks impressive on evenly spaced data can perform poorly on another sorted collection. They also check that endpoint equality never causes division by zero.

Maple compares alternatives using representative workloads and the actual storage arrangement. This fictional case illustrates evaluation design; it does not assert that interpolation search improves a particular database or production service.

Common misconceptions and mistakes

Sorted data automatically guarantees very fast interpolation search. The key distribution affects the quality of the estimated position.
The estimate is the answer. The stored key must still be checked.
Interpolation search returns a nearby value when the target is absent. Exact lookup should report absence unless a different interface is explicitly defined.
Duplicate keys require no special thought. They affect endpoint handling and which matching position the caller expects.

Business use

The classical average O(log log n) access result assumes an appropriate distribution model, notably uniformly distributed keys. Worst-case behavior can be linear in the number of entries. These are different statements, so a favorable average bound should not be presented as a universal guarantee.

For practical selection, include the cost of computing probes, memory access patterns, distribution changes and maintaining sorted order. Binary search offers a logarithmic worst-case comparison bound without relying on evenly distributed values. A decision should follow the workload and implementation constraints, not the appeal of a smaller asymptotic average expression.

Check your understanding

Why does the value 1000 make the estimate poor when searching for 7 in the second array?

Answer: The very large endpoint stretches the numerical range while almost all positions contain small values. Numerical distance no longer predicts index distance well.

Related terms

Binary search
Linear search
sorted array
search key
average-case analysis
worst-case analysis
interpolation
duplicate key

Learn next

Trace a lookup for 4 in the outlier array, recording each interval and probe. Then use binary search on the same array and compare the positions inspected without assuming that probe count equals total execution time.

Binary search

Sources

Perl, Itai and Avni analyze interpolation search and its distribution-dependent average behavior: https://csaws.cs.technion.ac.il/~itai/publications/Algorithms/p550-perl.pdf

NIST defines the algorithm and distinguishes its search strategy: https://xlinux.nist.gov/dads/HTML/interpolationSearch.html

The arrays, calculations and Maple Lookup case are original teaching examples. The complexity claims retain their average-case assumptions and worst-case qualification.

Previous: Interpolated precision Next: Interpolator