A
AiTechWorlds
AiTechWorlds
See Interpolation Search estimate the target position from value distribution, with synced code and live range.
def interpolation_search(a, target):
lo, hi = 0, len(a) - 1
while lo <= hi and a[lo] <= target <= a[hi]:
if a[hi] == a[lo]:
return lo if a[lo] == target else -1
pos = lo + (target - a[lo]) * (hi - lo) // (a[hi] - a[lo])
if a[pos] == target: return pos
if a[pos] < target: lo = pos + 1
else: hi = pos - 1
return -1Interpolation Search estimates the target position using the value distribution (like guessing a name near the front of a phone book), excelling on uniformly distributed sorted data.
| Best | O(1) |
| Average | O(log log n) |
| Worst | O(n) |
| Space | O(1) |
| Requires sorted | Yes |
The Interpolation Search Visualizer animates how Interpolation Search works: instead of always probing the middle, it estimates the target's position from the value distribution — like flipping near the front of a phone book for a name starting with 'A'. On uniformly distributed sorted data it averages O(log log n), but degrades to O(n) in the worst case. Space is O(1).
Set a target
Type the value to search for, or click New Array to randomize the sorted data and target.
Play the animation
Press Play to watch the estimated probe position jump based on value spacing.
Step and scrub
Use Step Forward/Back or the timeline to study each estimate.
Read the synced code
The highlighted pseudocode line shows the position formula; switch tabs for C++, Java, Python, or JavaScript.
100% Private — No Server Required
All processing happens directly in your browser. No data is uploaded, stored, or transmitted to any server.
Last reviewed on June 14, 2026 by the AiTechWorlds Tools Team. All processing runs locally in your browser.