Interpolation Search
Problem
Interpolation Search is an improved variant of binary search that works better for uniformly distributed data by estimating the position of the target value.
Examples:
Example 1:
Input: arr = [10, 20, 30, 40, 50, 60, 70, 80, 90], target = 70
Output: 6
Explanation: Interpolation Search estimates the position of 70 based on its value and finds it at index 6 in fewer steps than Binary Search.
Example 2:
Input: arr = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024], target = 64
Output: 6
Explanation: Interpolation Search estimates the position of 64 and finds it at index 6.
Solution
Intuition
- Interpolation Search improves on Binary Search by using the value of the target element to estimate its position.
- It works on the principle of 'probing' the position based on the value of the key being searched.
- For uniformly distributed data, it can achieve O(log log n) time complexity, which is better than Binary Search's O(log n).
- The algorithm is particularly useful when the elements are uniformly distributed.
Approach
- Calculate the probable position of the target using the formula: pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low])
- If the element at the calculated position is equal to the target, return the position.
- If the element is greater than the target, search in the left subarray.
- If the element is less than the target, search in the right subarray.
- Repeat until the element is found or the search space is exhausted.
Complexity Analysis
- Time Complexity: O(log log n) for uniformly distributed data, O(n) in worst case.
- Space Complexity: O(1) as it only uses a constant amount of extra space.
Implementation
CPP
Run your code to see output here