vizlearn
Home / Algorithms

Interpolation Search

Algorithms & Data StructuresBy Updated

An algorithm for searching in a sorted array that estimates the position of the target element based on the values at the current bounds, similar to how a human searches a dictionary.

Parameters

15

Visualization

Step: 0
Enter a target and click Step or Auto-Run.

Algorithm Insight

Predicts the location of the target mathematically:

pos = low + [(target - arr[low]) * (high - low) / (arr[high] - arr[low])]
  • 1. Calculate the probe position (pos).
  • 2. If arr[pos] == target, search is complete!
  • 3. If target is larger, low = pos + 1. If smaller, high = pos - 1.

Efficiency

Time (Avg) O(log log N)
Time (Worst) O(N)

Overview

Binary search always probes the midpoint. Interpolation search estimates a probe from the target’s value relative to the current endpoints. This can reduce work on sorted data with roughly uniform spacing, but performs poorly on clustered values.

Estimate a position

probe = low + (target - A[low]) * (high - low) / (A[high] - A[low])

The formula estimates where the target falls between the endpoint values. Compare A[probe] with the target and keep only the appropriate side, as in binary search.

For evenly spaced values [10, 20, 30, ..., 100], a target of 80 is estimated near its actual index. For highly uneven spacing, the estimate may be poor and the range may shrink by only one item at a time.

Use Array Size and Search Target, then press Reset Array and Next Step to see the probe move. Auto-Run completes the search. The array must be sorted in ascending order, and the probe must be clamped to the current bounds. If the endpoint values are equal, the denominator is zero; check for the target or stop before evaluating the formula.

Complexity and when to use it

For sorted data whose values are close to uniformly distributed, interpolation search can take about O(log log n) probes on average. That bound depends on the distribution assumption. In the worst case, such as strongly clustered or exponentially spaced values, it can take O(n) probes. Binary search has O(log n) worst-case time regardless of value distribution.

Choose interpolation search only when keys are numeric, sorted, and their spacing makes the estimate useful. For unknown or uneven distributions, binary search is the safer choice. Include the cost of sorting if the input is not already sorted.

Common mistakes with Interpolation Search

  • Using unsorted data: comparisons no longer identify a side to discard.
  • Assuming uniform spacing: skewed values can produce poor probes.
  • Ignoring equal endpoints: the position formula divides by zero.
  • Expecting it always to beat binary search: measure on the actual data and include setup costs.

Sources and next steps

Run it in Python

The same list searched twice: once evenly spaced, where guessing the position beats halving it, and once with a single outlier, where the same code degenerates to a linear scan.

interpolation_search.pyPython 3
Output
How the code works
  1. while lo <= hi and a[lo] <= target <= a[hi]:The second half of the condition is an early exit binary search does not have: if the target is outside the current window's value range, no probe inside it can succeed.
  2. fraction = (target - a[lo]) / (a[hi] - a[lo])How far along the window the target's value sits, between 0 and 1. Binary search always uses 0.5 here; this is the one line that makes the two algorithms different.
  3. pos = lo + int(fraction * (hi - lo))Turns that value fraction into an index, on the assumption that value and position rise together at a steady rate. When they do, the probe lands on or beside the answer immediately.
  4. if a[hi] == a[lo]: pos = loGuards a division by zero when every value in the window is equal. Reaching for a fraction of a zero-width value range is the crash this algorithm is famous for.
  5. skewed = [1, 2, ..., 5000]The outlier drags a[hi] so high that the computed fraction is nearly zero every time, so the probe advances one index per step. Interpolation search is O(log log n) on uniform data and O(n) on data like this.
Change one thing
  • Change the uniform target to 0 and to 190. Both ends are found in a step or two, where binary search needs its full log n.
  • Replace uniform with [i * i for i in range(20)] — sorted, but quadratically spaced. Watch the probe consistently undershoot.
  • Set fraction = 0.5 unconditionally. You have just written binary search, and on the skewed list it beats the clever version.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.




Predict, then reveal
About to run: set Array Size to its maximum (30). Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
  1. Interpolation search improves on binary search by:
  2. The program runs it on [1,2,3,4,5,6,7,8,9,5000] looking for 9. Why does it take so many steps?
  3. Its O(log log n) figure assumes the data is:





 Cheat sheet
Interpolation Search
Estimate where a value should sit instead of always splitting the middle, the way you open a phone book near the S pages.
ALGORITHMS · vizlearn.in/dsa/interpolation_search.html
More in Algorithms
AlgorithmsFibonacci SearchAlgorithmsBubble SortAlgorithmsSelection SortAlgorithmsInsertion Sort
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact