DSAverse

Searching Algorithms

Loading Searching Algorithms...

Search Visualization

sorted arrayindex 0

Interpolation Search

Estimates target position using value proportions — like a phone book lookup. O(log log n) for uniform data; degrades to O(n) for skewed distributions.

Visualization

Target:

Speed

Probe (est. pos)FoundSearch rangeEliminated

Target

Comparisons

1/0

Step

Ready — press Play or step through manually.

Complexity

O(1)

Best Case

O(log log n)

Average (uniform)

O(n)

Worst (skewed)

O(1)

Space

The Probe Formula

pos = low + floor((target - arr[low]) × (high - low) / (arr[high] - arr[low]))

•If target is 30% between arr[low] and arr[high] by value, probe at 30% of the index range
•Works perfectly when values are evenly spaced
•Degrades when values cluster or have large gaps

When to Use

✓Uniformly distributed numeric data (database indices, phone numbers)
✓When O(log log n) vs O(log n) matters at very large scale
✗Clustered, exponential, or unknown distributions
✗Non-numeric data (cannot interpolate strings directly)

Active Recall Quiz

Question 1 of 3

What type of data gives interpolation search its best-case O(log log n) performance?

DSAverse

Searching Algorithms

Loading Searching Algorithms...

Search Visualization

sorted arrayindex 0