Interpolation Search
Interpolation Search is an improved variant of binary search specifically optimized for uniformly distributed sorted arrays. Instead of always checking the middle element, it estimates the target's position based on the target value relative to the range of values, similar to how humans search a phone book. Achieves O(log log n) average time for uniformly distributed data, significantly faster than binary search's O(log n).
Visualization
Interactive visualization for Interpolation Search
Interpolation Search
Uniformly Distributed Array:
• Time: O(log log n) for uniform distribution
• Uses value-based position estimation
• Best for uniformly distributed data
Interactive visualization with step-by-step execution
Implementation
1function interpolationSearch(arr: number[], target: number): number {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left <= right && target >= arr[left] && target <= arr[right]) {
6 if (left === right) {
7 return arr[left] === target ? left : -1;
8 }
9
10 const pos = left + Math.floor(
11 ((target - arr[left]) * (right - left)) / (arr[right] - arr[left])
12 );
13
14 if (arr[pos] === target) return pos;
15 if (arr[pos] < target) left = pos + 1;
16 else right = pos - 1;
17 }
18
19 return -1;
20}Deep Dive
Theoretical Foundation
Interpolation Search uses linear interpolation to estimate position: pos = low + [(target - arr[low]) / (arr[high] - arr[low])] × (high - low). This formula assumes uniform distribution, placing pos proportionally between low and high based on the target value. For uniformly distributed data, each probe eliminates roughly √n elements instead of half, giving O(log log n) average complexity. However, worst case is O(n) for non-uniform distributions (e.g., exponential data). Best for large, uniformly distributed datasets like phone directories, dictionaries, or numerical databases.
Complexity
Time
O(1)
O(log log n)
O(n)
Space
O(1)
Applications
Industry Use
Phone directory lookups
Dictionary and encyclopedia searches
Large numerical databases
Search engines for uniformly distributed IDs
Database index probing
Use Cases
Related Algorithms
Binary Search
Binary Search is one of the most efficient searching algorithms with O(log n) time complexity. It works on sorted arrays by repeatedly dividing the search space in half, eliminating half of the remaining elements with each comparison. This divide-and-conquer approach makes it exponentially faster than linear search for large datasets.
Linear Search
Linear Search, also known as Sequential Search, is the simplest searching algorithm that checks each element in a list sequentially until the target element is found or the end is reached. Despite its O(n) time complexity, it's the only option for unsorted data and remains practical for small datasets or when simplicity is crucial.
Jump Search
Jump Search is an efficient algorithm for sorted arrays that combines the benefits of linear and binary search. Instead of checking every element (linear) or dividing the array (binary), it jumps ahead by fixed steps of √n and then performs linear search within the identified block. This approach achieves O(√n) time complexity, making it faster than linear search while being simpler than binary search for certain applications.
Exponential Search
Combines exponential growth with binary search. Especially useful for unbounded/infinite arrays.