Interpolation Search
Estimates where the target should be from its value, like opening a dictionary near the right letter, and narrows in from there.
How it works
Binary search always checks the middle. Interpolation search guesses instead, the way you'd open a dictionary near the back to look up "window". It keeps a range, low to high, and reads the values at both ends. If the target is outside them, it can't be in the range. Otherwise it estimates the position from how far the target sits between the two end values:
pos = low + (target - array[low]) × (high - low) / (array[high] - array[low])
If the target is 30% of the way from the lowest to the highest value, it guesses 30% of the way into the range. Then it checks that position, just like binary search:
- If it equals the target, it returns that index.
- If it is smaller, the range moves past it (
low = pos + 1). - If it is larger, the range ends before it (
high = pos - 1).
When the range is empty, or the target falls outside the end values, it returns -1.
When to use it
Interpolation search is fastest on large sorted arrays whose values are evenly spread out, like IDs, timestamps or phone numbers, where the guesses land very close. On unevenly spread values (say, mostly small numbers and a few huge ones), the guesses keep landing near one end and it can slow down to a linear scan. Binary search's O(log n) is guaranteed, so it's the safer default.
Complexity
| Case | Time | When |
|---|---|---|
| Best | O(1) | The first guess lands on the target |
| Average | O(log log n) | Values are evenly spread out |
| Worst | O(n) | Values are very unevenly spread, so each guess moves by one |
| Extra space | Why |
|---|---|
| O(1) | It only keeps the low, high and pos indexes |
Implementations
function interpolationSearch(array, target) {
let low = 0;
let high = array.length - 1;
while (low <= high) {
const lowValue = array[low];
const highValue = array[high];
if (target < lowValue || target > highValue) return -1;
if (lowValue === highValue) return lowValue === target ? low : -1;
const pos = low + Math.floor(((target - lowValue) * (high - low)) / (highValue - lowValue));
const value = array[pos];
if (value === target) return pos;
if (value < target) {
low = pos + 1;
} else {
high = pos - 1;
}
}
return -1;
}
def interpolation_search(array, target):
low, high = 0, len(array) - 1
while low <= high:
low_value, high_value = array[low], array[high]
if target < low_value or target > high_value:
return -1
if low_value == high_value:
return low if low_value == target else -1
pos = low + (target - low_value) * (high - low) // (high_value - low_value)
value = array[pos]
if value == target:
return pos
if value < target:
low = pos + 1
else:
high = pos - 1
return -1
#include <vector>
int interpolationSearch(const std::vector<int>& a, int target) {
int low = 0;
int high = static_cast<int>(a.size()) - 1;
while (low <= high) {
if (target < a[low] || target > a[high]) return -1;
if (a[low] == a[high]) return a[low] == target ? low : -1;
long long offset = static_cast<long long>(target - a[low]) * (high - low) / (a[high] - a[low]);
int pos = low + static_cast<int>(offset);
if (a[pos] == target) return pos;
if (a[pos] < target) {
low = pos + 1;
} else {
high = pos - 1;
}
}
return -1;
}