Time Complexity
Best: O(1)
Avg: O(log log n)
Worst: O(n)
Interpolation Search is an improved variant of Binary Search for uniformly distributed sorted data. Instead of always going to the middle, it estimates the position of the target based on its value.
How it works:
1. Estimate position: pos = low + ((target - arr[low]) × (high - low)) / (arr[high] - arr[low])
2. If arr[pos] equals target, return pos
3. If arr[pos] < target, search right portion
4. If arr[pos] > target, search left portion
Time Complexity:
Best: O(1)
Average: O(log log n) — for uniform distribution
Worst: O(n) — for non-uniform distribution
Space Complexity: O(1)
Properties:
- Requires sorted array
- Best for uniformly distributed data
- Can degrade to O(n) for skewed distributions
Interpolation Search can be significantly faster than Binary Search when data is uniformly distributed, as it makes better guesses about where the target might be.
Related algorithms
Frequently asked questions
- What is Interpolation Search?
- Interpolation Search is an improved variant of Binary Search for uniformly distributed sorted data. Instead of always going to the middle, it estimates the position of the target based on its value.
- What is the complexity of Interpolation Search?
- Time (average): O(log log n) — for uniform distribution · Space: O(1)
- Who is this Interpolation Search visualizer for?
- The Interpolation Search visualization targets intermediate-level learners in the Searching category. Useful for students, interview prep, and hands-on review.
- What algorithms are related to Interpolation Search?
- In the same category (Searching) you can explore: Binary Search, Linear Search, Jump Search. Each has an interactive visualization.