Interpolation Search
Interpolation Search uses a formula to predict where the target likely is — like how a human opens a dictionary near "Z" for a word starting with Z. On uniformly distributed data it achieves O(log log n), beating Binary Search. Watch the Probe (P) jump directly toward the target.
Search Target
↑ Set a target value above to begin searching the array
Legend
Inspector
Legend
Inspector
Reference implementation of Interpolation Search. Select a language tab to view and copy the code.
int interpolation_search(int arr[], int n, int target) {
int low = 0, high = n - 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
if (low == high) {
return (arr[low] == target) ? low : -1;
}
/* Estimate position using linear interpolation */
int pos = low + ((target - arr[low]) *
(high - low)) / (arr[high] - arr[low]);
if (arr[pos] == target) return pos;
if (arr[pos] < target) low = pos + 1;
else high = pos - 1;
}
return -1;
}#include <vector>
int interpolationSearch(const std::vector<int>& arr, int target) {
int low = 0, high = static_cast<int>(arr.size()) - 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
if (low == high)
return (arr[low] == target) ? low : -1;
int pos = low + ((target - arr[low]) *
(high - low)) / (arr[high] - arr[low]);
if (arr[pos] == target) return pos;
if (arr[pos] < target) low = pos + 1;
else high = pos - 1;
}
return -1;
}public static int interpolationSearch(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
if (low == high)
return (arr[low] == target) ? low : -1;
int pos = low + ((target - arr[low]) *
(high - low)) / (arr[high] - arr[low]);
if (arr[pos] == target) return pos;
if (arr[pos] < target) low = pos + 1;
else high = pos - 1;
}
return -1;
}def interpolation_search(arr: list[int], target: int) -> int:
low, high = 0, len(arr) - 1
while low <= high and arr[low] <= target <= arr[high]:
if low == high:
return low if arr[low] == target else -1
# Probe position via linear interpolation
pos = low + (target - arr[low]) * (high - low) // (arr[high] - arr[low])
if arr[pos] == target:
return pos
elif arr[pos] < target:
low = pos + 1
else:
high = pos - 1
return -1function interpolationSearch(arr, target) {
let low = 0, high = arr.length - 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
if (low === high)
return arr[low] === target ? low : -1;
// Probe position via linear interpolation
const pos = low + Math.floor(
(target - arr[low]) * (high - low) / (arr[high] - arr[low])
);
if (arr[pos] === target) return pos;
if (arr[pos] < target) low = pos + 1;
else high = pos - 1;
}
return -1;
}Python — Code Walkthrough
Chained comparison for the range guard
arr[low] <= target <= arr[high]Python allows chaining comparison operators. arr[low] <= target <= arr[high] reads naturally and is equivalent to arr[low] <= target and target <= arr[high].
Floor division // prevents float index
pos = low + (target - arr[low]) * (high - low) // (arr[high] - arr[low])Python's / operator returns a float. Using // (floor division) keeps pos an integer suitable for use as an index. Python's arbitrary-precision integers also prevent overflow.
Division-by-zero guard
if low == high: return low if arr[low] == target else -1When low equals high, arr[high] − arr[low] = 0 which would raise ZeroDivisionError. This check handles the degenerate one-element window.
elif chain for clarity
if arr[pos] == target ... elif arr[pos] < target ... elseThree mutually exclusive outcomes: found (return pos), probe too low (advance low), probe too high (retreat high). Python elif avoids nested ifs.