Interpolation Search
Algorithm · Stretch
Step through it: Modified Binary Search pattern
target = 23
Step 1 of 6
Goal: find 23 in this sorted list. Checking one number at a time could take 7 looks, and a million numbers would take up to a million. Because the list is sorted, we can do far better.
Step 2 of 6
Look at the middle number first. The middle of positions 0 to 6 is position 3, which holds 12.
Step 3 of 6
12 is smaller than 23, and the list is sorted, so 23 cannot be at or before 12. Throw away that whole half. Only positions 4 to 6 are left.
Step 4 of 6
Do the same thing on what is left. The middle of positions 4 to 6 is position 5, which holds 23. Found it.
Step 5 of 6
Two looks instead of up to seven. Every look halves what is left, so a million numbers need only about 20 looks. Halving the search area each time is called binary search.
Step 6 of 6
Your turn. Pick a target and press Next to watch each look. Try 7: it is not in the list.
Complexity
Time Complexity
O(log(log(n))
Interpolation search is an algorithm for searching for a key in an array that has been ordered by numerical values assigned to the keys (key values).
For example we have a sorted array of n uniformly distributed values arr[],
and we need to write a function to search for a particular element x in the array.
Linear Search finds the element in O(n) time, Jump Search takes O(√ n) time
and Binary Search take O(Log n) time.
The Interpolation Search is an improvement over Binary Search for instances, where the values in a sorted array are uniformly distributed. Binary Search always goes to the middle element to check. On the other hand, interpolation search may go to different locations according to the value of the key being searched. For example, if the value of the key is closer to the last element, interpolation search is likely to start search toward the end side.
To find the position to be searched, it uses following formula:
// The idea of formula is to return higher value of pos
// when element to be searched is closer to arr[hi]. And
// smaller value when closer to arr[lo]
pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[Lo]))
arr[] - Array where elements need to be searched
x - Element to be searched
lo - Starting index in arr[]
hi - Ending index in arr[]Code
/**
* Interpolation search implementation.
*
* @param {*[]} sortedArray - sorted array with uniformly distributed values
* @param {*} seekElement
* @return {number}
*/
export default function interpolationSearch(sortedArray, seekElement) {
let leftIndex = 0;
let rightIndex = sortedArray.length - 1;
while (leftIndex <= rightIndex) {
const rangeDelta = sortedArray[rightIndex] - sortedArray[leftIndex];
const indexDelta = rightIndex - leftIndex;
const valueDelta = seekElement - sortedArray[leftIndex];
// If valueDelta is less then zero it means that there is no seek element
// exists in array since the lowest element from the range is already higher
// then seek element.
if (valueDelta < 0) {
return -1;
}
// If range delta is zero then subarray contains all the same numbers
// and thus there is nothing to search for unless this range is all
// consists of seek number.
if (!rangeDelta) {
// By doing this we're also avoiding division by zero while
// calculating the middleIndex later.
return sortedArray[leftIndex] === seekElement ? leftIndex : -1;
}
// Do interpolation of the middle index.
const middleIndex = leftIndex + Math.floor((valueDelta * indexDelta) / rangeDelta);
// If we've found the element just return its position.
if (sortedArray[middleIndex] === seekElement) {
return middleIndex;
}
// Decide which half to choose for seeking next: left or right one.
if (sortedArray[middleIndex] < seekElement) {
// Go to the right half of the array.
leftIndex = middleIndex + 1;
} else {
// Go to the left half of the array.
rightIndex = middleIndex - 1;
}
}
return -1;
}References
Practice
Modified Binary Search
- Binary SearchEasy
- Search Insert PositionEasy
- Sqrt(x)Easy
- First Bad VersionEasy
- Valid Perfect SquareEasy
- Arranging CoinsEasy
- Search in Rotated Sorted ArrayMedium
- Find Minimum in Rotated Sorted ArrayMedium
- Find First and Last Position of Element in Sorted ArrayMedium
- Find Peak ElementMedium
- Search a 2D MatrixMedium
- Koko Eating BananasMedium
- Capacity To Ship Packages Within D DaysMedium
- Time Based Key-Value StoreMedium
- Single Element in a Sorted ArrayMedium
- Minimum Number of Days to Make m BouquetsMedium
- Median of Two Sorted ArraysHard
- Split Array Largest SumHard
- Find Minimum in Rotated Sorted Array IIHard
Spotted a mistake or something unclear? Report it on GitHub.