Back to Searching

Interpolation Search Visualizer

Watch how Interpolation Search estimates the position using linear interpolation, ideal for uniformly distributed data.

Time: O(log log n)
Space: O(1)
Requirement: Sorted & Uniform
Linear Interpolation
Search Range: [0, 14] | Comparisons: 0
0
10
L
1
12
2
13
3
16
4
18
5
19
6
20
7
21
8
22
9
23
10
24
11
33
12
35
13
42
14
47
R
Target: 18 | Step: 1 of 0

Current Step:

Click Start to begin Interpolation Search visualization

Interpolation Search

Time Complexity:O(log log n)
Space Complexity:O(1)
Worst Case:O(n)
Best For:Uniform Data

Color Legend

Interpolated Position
Search Boundaries (L, R)
Target Found
Active Search Space
Eliminated Space

Interpolation Formula

pos = left + [(target - arr[left]) × (right - left)] / (arr[right] - arr[left])

This formula estimates where the target should be based on its value relative to the range.

Works best when data is uniformly distributed.

How It Works

  1. 1Calculate interpolated position
  2. 2Check element at calculated position
  3. 3Adjust search range based on comparison
  4. 4Repeat until found or exhausted

Python Implementation

def interpolation_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while (left <= right and target >= arr[left] and target <= arr[right]):
        # If we have a single element
        if left == right:
            if arr[left] == target:
                return left
            else:
                return -1
        
        # Interpolation formula
        pos = left + int(((target - arr[left]) * (right - left)) / (arr[right] - arr[left]))
        
        if arr[pos] == target:
            return pos
        elif arr[pos] < target:
            left = pos + 1
        else:
            right = pos - 1
    
    return -1

Real-world Applications

  • • Searching in phone directories
  • • Database indexing for numeric ranges
  • • Time-series data analysis
  • • Geographic coordinate searching
  • • Uniformly distributed scientific data
  • • Dictionary/glossary lookups