1. Target in range
Only estimate while the target can be between the low and high values.
target >= arr[low] && target <= arr[high]Typorithm · hard
Interpolation Search
▷ Interactive algorithm labinterpolation-searchsearchsorted-arrayestimated-positionnumeric-search
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Interpolation Search
Search Algorithms
Interpolation Search estimates the target's position inside a sorted numeric range instead of always using the middle.
Interpolation Search works on sorted numeric data.
It estimates where the target should be based on low and high values.
This can be very fast when values are uniformly distributed.
It needs guards for out-of-range targets and equal low/high values.
Preparing algorithm lab…
01
Requires sorted numeric values.
02
Estimate position from value range.
03
Move boundaries around the estimate.
04
Fast on uniform data.
05
Can degrade on uneven distributions.
function interpolationSearch(arr, target) {
let low = 0;
let high = arr.length - 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
if (arr[low] === arr[high]) {
return arr[low] === target ? low : -1;
}
const position = low + Math.floor(
((target - arr[low]) * (high - low)) / (arr[high] - arr[low])
);
if (arr[position] === target) return position;
if (arr[position] < target) low = position + 1;
else high = position - 1;
}
return -1;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Flat range guard
Avoid dividing by zero when all remaining values are equal.
if (arr[low] === arr[high])3. Estimated position
Estimate where target should be based on its value within the current range.
const position = low + Math.floor(4. Hit check
Return immediately if the estimated position is correct.
if (arr[position] === target) return position5. Move low
If the estimate is too small, search to the right.
low = position + 16. Move high
If the estimate is too large, search to the left.
high = position - 1A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.