CoreSource checked

Interpolation Search

Searches sorted numeric data by estimating where the target should be.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Searching
Difficulty: Intermediate
Family: Probe Search
Tier: Core
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 1
Relationships: 1
Code example: Ready
Visualization: Ready

Overview

Interpolation Search uses the target value and the range endpoints to guess a likely position before narrowing the range.

Core Concepts

candidate searchsorted search spacenumeric approximationprobe searchcandidate spacematch testsearch interval

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(1)

Average

O(log log n)

Worst

O(n)

Space

O(1)

When to Use

Use Interpolation Search when you need to estimate a target position.
Use it when the input assumptions match the method's model.
Use it when you need a clear lookup strategy for known input organization.
Use it when the method's tradeoffs fit the workload.

When Not to Use

Avoid it when the input cannot be kept sorted cheaply.
Avoid it when maintaining the required data layout costs more than the lookup saves.
Do not treat the O(log log n) average case as a guarantee; check the O(n) worst case.
Avoid it when the required output is not index of target.

What It Does

Estimates a target position
Narrows a sorted numeric range

Use Cases

Searching uniformly distributed numbers
Finding numeric keys
Reducing probes in large sorted arrays

Inputs

Sorted numeric array
Target value

Outputs

Index of target
Not-found result

Key Formulas (1)

Interpolated probe

pos = low + ((target − values_[low]) · (high − low)) / (values_[high] − values_[low])

pos = low + ((target - values[low]) * (high - low)) / (values[high] - values[low])

Estimates where the target should fall when values are roughly evenly distributed.

Pseudocode

1.Keep low and high bounds
2.Estimate the target position from endpoint values
3.Compare the estimated position with the target
4.Move the low or high bound
5.Repeat until found or out of range

Canonical Example

Input: values = [2, 5, 8, 12, 16], target = 12
Output: index = 3
Explanation: Interpolation Search: The search checks candidate positions until it identifies the target value.

Implementation Notes

Keep the input contract explicit: Sorted numeric array; Target value.
Decide up front whether not-found results return null, -1, false, or an insertion position.
Search algorithms should define both success and failure semantics.

Common Pitfalls

Interpolation Search is best when values are fairly evenly distributed.
Handle empty, invalid, and boundary inputs before trusting index of target.
Off-by-one bounds, duplicates, and missing-target behavior should be specified before implementation.

Interactive Mechanism Walkthrough

Indexed Interval & Boundary Probe

Show the probe jumping near the expected target position.

Target key: 41low=0, mid=4, high=9

4[0]

9[1]

15[2]

22[3]

27[4]

34[5]

41[6]

49[7]

58[8]

63[9]

Step 1 of 5: Keep low and high bounds

estimated-search

Notes

Interpolation Search operates in O(log log n) time and O(1) space within the Probe Search family. Key governing relation: pos = low + ((target - values[low]) * (high - low)) / (values[high] - values[low]). Often compared with Binary Search and Linear Search.

Sources (2)

What each reference supports for this entry.

The Art of Computer Programming, Volume 3

Book

Searching reference for Interpolation Search's probe strategy, comparison model, and expected or worst-case behavior.