VietMX Staff asked 3 years ago
Interpolation Search is an algorithm similar to Binary Search for searching for a given target value in a sorted array. It is an improvement over Binary Search for instances, where the values in a sorted array are uniformly distributed.
The binary search always chooses the middle of the remaining search space. On a contrast Interpolation search, at each search step, calculates (using interpolation formula) where in the remaining search space the target might be present, based on the low and high values of the search space and the value of the target. 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. The value actually found at this estimated position is then compared to the target value. If it is not equal, then depending on the comparison, the remaining search space is reduced to the part before or after the estimated position.
The idea of the interpolation formula or partitioning logic is to return higher value of pos when element to be searched is closer to arr[hi]. And smaller value when closer to arr[low].
arr[] ==> Array where elements need to be searched
x ==> Element to be searched
low ==> Starting index in arr[]
hi ==> Ending index in arr[]
pos = low + [ (x-arr[low])*(hi-low) / (arr[hi]-arr[Low]) ]
In the interpolation search algorithm, the midpoint is computed in such a way that it gives a higher probability of obtaining our search term faster. The worst case complexity of interpolation search is O(n). However, its average case complexity, under the assumption that the keys are uniformly distributed, is _O(log log N).
It can be proven that Interpolation Search repeatedly reducing the problem to a subproblem of size that is the square root of the original problem size, and algorithm will terminate after O(log log n) steps (see proof here). When the values are equally dispersed into the interval this search algorithm can be extremely useful – way faster than the binary search (that divides searching space by half).
const interpolationSearch = (array, key) => {
// if array is empty.
if (!array.length) {
return -1;
}
let low = 0;
let high = array.length - 1;
while (low <= high && key >= array[low] && x <= array[high]) {
// calculate position with
let pos = low + Math.floor(((high - low) * (key - array[low])) / (array[high] - array[low]));
// if all elements are same then we'll have divide by 0 or 0/0
// which may cause NaN
pos = Number.isNaN(pos) ? low : pos;
if (array[pos] === key) {
return pos;
}
if (array[pos] > key) {
high = pos - 1;
} else {
low = pos + 1;
}
}
// not found.
return -1;
};