cf.completefrontend
SEARCHING & BINARY SEARCH · ADVANCED

Interpolation search

Search a sorted list of evenly spread numbers by guessing where the target should be from its value, like opening a phone book near the right letter.

Time O(log log n) on evenly spread dataSpace O(1)2 practice problemsStep-through picture

The idea

Binary search always checks the middle. But if you look up "Zhang" in a phone book, you don't open it in the middle. You open it near the end, because Z is near the end of the alphabet. Interpolation search does the same with numbers.

In a sorted list from items[low] to items[high], if the values are spread evenly, the target should sit about (target - items[low]) / (items[high] - items[low]) of the way along. That fraction times the number of positions gives a guess, pos. If the guess is wrong, the search moves low or high past it and guesses again in the smaller range.

On evenly spread data, the guesses are so good that the search needs about log(log n) steps, which is only 5 for a billion items. On badly spread data, such as [1, 2, 3, 4, 1000], the guesses can be poor and the search can take n steps.

An everyday example

Opening a dictionary near the right page

To find the word "melon" in a dictionary, you open it a bit before the middle, because M is about halfway through the alphabet. You land on "magnet", a little early, so you look a bit further on. To find "apple" you open it near the front. You use what the word is to guess where it is, instead of always opening to the exact middle.

How the example maps to the code
In the exampleIn the code
Where M falls in the alphabet(target - items[low]) / (items[high] - items[low])
The page you open topos
Landing a little early: look laterlow = pos + 1
Landing a little late: look earlierhigh = pos - 1

From the slow way to interpolation search

  1. Binary search always checks the middle, whatever the values are. Looking for 45 in a list that runs from 5 to 88, it doesn't use the fact that 45 is about halfway between those two values. The values themselves hint at where the target sits, and binary search ignores that hint.
  2. If the values rose by the same amount at every step, you could compute the position exactly. With values from items[low] to items[high] spread evenly over high - low steps, the target sits the fraction (target - items[low]) / (items[high] - items[low]) of the way along. Multiply that by high - low, round down, and add low: that is the guess pos.
  3. Real data is rarely perfectly even, so the guess may miss. But a miss still tells you which side to keep, just like a binary search check: if items[pos] < target, the target is after pos. Then compute a new guess from the new ends, which sit closer to the target and usually give a better line.
  4. Two guards keep it safe: stop when the target is outside items[low] to items[high], which also keeps pos inside the range, and handle the case where both ends are equal, which would divide by zero. Guess from the values, check, keep the side that can hold the target: that loop is interpolation search.

How it works

  1. Set low = 0 and high = items.length - 1.
  2. While the target is between items[low] and items[high], estimate its position: pos = low + Math.floor((target - items[low]) * (high - low) / (items[high] - items[low])).
  3. If items[pos] is the target, return pos.
  4. If items[pos] is smaller, the target is to the right: low = pos + 1.
  5. If it is bigger, the target is to the left: high = pos - 1.
  6. If all values in the range are equal, avoid dividing by zero: just compare items[low] with the target.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function interpolationSearch(items, target) {
  2. let low = 0;
  3. let high = items.length - 1;
  4. while (low <= high && target >= items[low] && target <= items[high]) {
  5. if (items[high] === items[low]) {
  6. return items[low] === target ? low : -1;
  7. }
  8. const pos = low + Math.floor(
  9. ((target - items[low]) * (high - low)) / (items[high] - items[low])
  10. );
  11. if (items[pos] === target) return pos;
  12. if (items[pos] < target) {
  13. low = pos + 1;
  14. } else {
  15. high = pos - 1;
  16. }
  17. }
  18. return -1;
  19. }

How fast it is

TimeO(log log n) on evenly spread data
Extra memoryO(1)

On evenly spread data, each guess lands very close to the target, so the range shrinks extremely fast. When a few huge or tiny values skew the line, each guess may only move one step.

  • Best caseO(1)

    The values are perfectly even, such as [12, 24, 36, 48, ...], so the first guess is exact.

  • Average caseO(log log n)

    The values are spread fairly evenly, like random numbers drawn from one range. On a sorted list of a million random numbers, a test run needed about 4 guesses on average, against about 20 checks for binary search.

  • Worst caseO(n)

    A few huge values bend the line, such as the numbers 0 to 999,998 followed by 10^15. Finding 999,998 in that list took 999,999 guesses in a test run, one step at a time.

Common mistakes

  • Dividing by items[high] - items[low] when it is 0. Handle the "all equal" range first.
  • Dropping the target >= items[low] && target <= items[high] check. A target outside the range makes pos point outside the list.
  • Computing the fraction with integer-style rounding too early, such as Math.floor((target - items[low]) / (items[high] - items[low])) * (high - low). The fraction rounds to 0 and every guess is low. Multiply first, then divide and round.
  • Using it on strings or on data with a few huge outliers. Binary search is safer there.

When to use it

Look for these clues in a problem:

  • The list is sorted and its values are spread fairly evenly, such as IDs, timestamps at a steady rate, or positions on a grid.
  • The list is very large and you want fewer checks than binary search.
  • You can compute how far apart two values are, so they are numbers, not just comparable items.

Check yourself

Answer each one in your head first, then open it.

In [10, 20, 30, 40, 50], where does the first guess for 40 land?

pos = 0 + Math.floor((40 - 10) * 4 / (50 - 10)) = 3, and items[3] is 40, so one guess is enough.

Why must the loop check target >= items[low] && target <= items[high]?

It keeps the fraction between 0 and 1, so pos stays inside the range. It also stops the search as soon as the target can't be in the range.

Why does one huge value at the end slow it down so much?

It stretches the gap items[high] - items[low], so every fraction is tiny and every guess lands near low. Each guess then drops only a few items.

What does O(log log n) mean for a billion items?

log₂ of a billion is about 30, and log₂ 30 is about 5. So on even data it needs about 5 guesses where binary search needs about 30.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 2 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The promise is the one from binary search: if target is in the list, it is somewhere from low to high. The loop also checks that target is between items[low] and items[high]. If it isn't, the sorted order means it can't be in the range, so returning -1 is right.

That check also keeps the guess inside the range. The fraction (target - items[low]) / (items[high] - items[low]) is between 0 and 1, so pos is between low and high. From there each step works like binary search: if items[pos] < target, everything up to pos is too small, so low = pos + 1 keeps the promise, and the other side works the same way.

The loop ends because each step leaves pos out, so the range shrinks by at least one. The speed depends on the data, but the correctness doesn't: even the worst guess drops at least one item and never drops the target. That is why skewed data makes it slow, but never wrong.

Going deeper

3 more ideas

Where the guess comes from

Draw a straight line from the point (low, items[low]) to the point (high, items[high]). If the values are spread evenly, every item sits on that line. The guess pos is where the line reaches the height target. That is what "interpolation" means: estimating a point between two known points.

When it gets slow

Find 9 in [1, 2, 3, 4, 5, 6, 7, 8, 9, 1000]. The huge last value drags every guess to the left: the first guess is Math.floor(8 * 9 / 999) = 0, then 1, then 2, one step at a time. It takes 9 guesses, as slow as a linear search. On uneven data, binary search is safer.

Why the loop checks the range first

The loop only runs while target >= items[low] and target <= items[high]. This keeps pos inside low..high: the fraction is between 0 and 1. Without this check, a target outside the range gives a pos outside the list.

Work it by hand

Every step in a table, with why

Look for 45 in a sorted list of 10 numbers whose last gap is much bigger than the others.

items = [5, 9, 14, 20, 23, 30, 41, 45, 52, 88], target = 45

SteplowhighGuesspositems[pos]What happensWhy
109(45 - 5) * 9 / (88 - 5) is about 4.3442323 < 45, so low = 5The guess lands too early. The last gap, from 52 to 88, is much bigger than the rest, which bends the line and pulls every guess to the left.
259(45 - 30) * 4 / (88 - 30) is about 1.0364141 < 45, so low = 7The new ends are 30 and 88. The fraction part rounds down to 1, so pos = 5 + 1 = 6. Still too early, but closer.
379(45 - 45) * 2 / (88 - 45) is 0745Match: return 7Now items[low] is 45 itself, so the guess is low. Found.

It returns 7 after 3 guesses. Binary search would need only 2 checks here, because the one large gap at the end makes the straight line a poor fit. On even data the first guess is often exact: in [12, 24, 36, 48, 60, 72, 84, 96], 72 is found at pos = 5 with one guess.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Interpolation searchO(log log n)O(1)Huge sorted lists of evenly spread numbers, where every read is expensive, such as reads from disk.
Binary searchO(log n)O(1)Any sorted list, including uneven values and strings. Its speed never depends on the data.
Direct index from a formulaO(1)O(1)The values are perfectly regular, so the position can be computed in one step.

Extra memory: O(1): low, high, and pos.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Interpolation search and the other approaches, on a scale where each line up is 10 times more steps.
  • Interpolation search O(log log n)
  • Binary search O(log n)
  • Direct index from a formula O(1)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Interpolation search234
Binary search31020
Direct index from a formula111

Inputs that need care

5 tricky inputs
All values equal: [7, 7, 7]
items[high] - items[low] is 0, so the formula would divide by zero. The code checks items[high] === items[low] first and returns low if that value is the target, else -1.
A target outside the values: [5, 9, 14], target 2 or 20
The loop condition fails before any guess, and it returns -1 at once. Without that check, pos would be negative or past the end.
An empty list: items = []
high is -1, so low <= high is false and it returns -1. The reads of items[low] are never reached, because && stops at the first false part.
A missing target between values: the trace's list, target 43
Guesses land on 23, 30, and 41. Then low becomes 7, where items[7] = 45 is bigger than 43, so the loop condition fails and it returns -1.
Dates or strings
Convert dates to numbers with getTime() first, so the formula can measure gaps. Strings have no simple "how far apart" measure, so search them with binary search instead.

Variations and follow-ups

Twists interviewers add

Mixing in binary search steps

A safer version alternates: one interpolation guess, then one binary search check in the middle of what's left. The binary step makes sure the range at least halves every two steps, so the worst case becomes O(log n), while even data still gets the fast guesses.

An index from a known rate

When the data is perfectly regular, like log lines every 5 seconds or rows of fixed height, the first guess is always exact and no loop is needed: index = Math.floor((time - start) / 5). That is interpolation with a known line.

Straightening uneven data

If values grow along a known curve, such as i * i * i, the line is a poor fit: in a test on a million such values, plain interpolation needed about 250 guesses on average. Searching on Math.cbrt(items[i]) instead makes the values even again, and the guesses become good.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "uniformly distributed", "evenly spaced", or a sorted list of numbers where the question hints that you can beat O(log n).
  • Explain the guess as a straight line between the points (low, items[low]) and (high, items[high]), and say where that line reaches the height target. Then say the rest is binary search with a smarter choice of mid.
  • Name the risks up front: dividing by zero when the ends are equal, a guess outside the range when the target is outside the values, and O(n) time on skewed data. Interviewers mostly ask about the last one.
  • The usual follow-up is "why don't standard libraries use it?". Answer: real data is often uneven, the worst case is linear, and each step needs a multiply and a divide. Binary search's steady O(log n) is the safer default.

Where frontend code uses it

The same idea in real UI code
  • A virtualized list with a fixed row height finds the first visible row with Math.floor(scrollTop / rowHeight). That is interpolation search where the first guess is always exact, because the rows are perfectly even.
  • Seeking in a video with a steady frame rate: the frame for a time is about time × fps, a direct guess instead of a search.
  • Looking up a log entry by timestamp when events arrive at a steady rate: guess the index from the time, then fix it up with a few steps.

Related algorithms