cf.completefrontend
SEARCHING & BINARY SEARCH · ADVANCED

Exponential search

Find a range that holds the target by doubling a bound (1, 2, 4, 8...), then binary search inside that range.

Time O(log i)Space O(1)2 practice problemsStep-through picture

The idea

Binary search needs to know where the list ends. Sometimes you don't know that, such as a feed that loads more items as you scroll, or a list so long that it is better to start small. Exponential search handles this.

It first looks at index 1, then 2, then 4, then 8, doubling each time, until it finds an item that is not smaller than the target (or runs past the end). Now the target, if present, must sit between the previous bound and this one. Then it runs a normal binary search in that small range.

If the target is near the start, this is faster than plain binary search over the whole list. A target at index i is found in about 2 × log i steps, however long the list is.

An everyday example

Finding a page in a book with no page count

You need page 300 in a huge book whose last page you don't know. You flip to page 1, then 2, 4, 8, 16, and so on, doubling each time. At page 256 you are still too early, but page 512 is past it. Now you know page 300 is between 256 and 512, and you can split that gap in half again and again.

How the example maps to the code
In the exampleIn the code
Doubling the page you flip tobound *= 2
Page 512 is past the one you wantitems[bound] >= target stops the doubling
The gap from 256 to 512low = Math.floor(bound / 2) to high = bound
Halving the gapThe binary search loop

From the slow way to exponential search

  1. Binary search needs both ends of the range before it starts. For a feed that keeps loading, or a sorted list with no known length, there is no high to start from. The obvious fix is to walk forward from index 0 until you pass the target, which costs i checks for a target at index i.
  2. Walking one step at a time is slow because each step rules out only one item. Doubling the step instead, checking indexes 1, 2, 4, 8, 16, reaches index i after only about log₂ i checks. You stop at the first bound where items[bound] is not smaller than the target, or where bound runs past the end.
  3. When the doubling stops, you know two things. The item at bound / 2 was smaller than the target, because it was checked on the step before (or it is index 0), and items[bound] is not smaller, or doesn't exist. So the target, if present, sits between bound / 2 and bound: a range of about i / 2 items with both ends known.
  4. Run plain binary search on that range, which takes about log₂ i more checks. The total cost depends on where the target is, not on how long the list is. Doubling to find a range, then binary search inside it: that loop is exponential search.

How it works

  1. If the list is empty, return -1.
  2. Start with bound = 1.
  3. While bound is inside the list and items[bound] is smaller than the target, double it: bound *= 2.
  4. The target can only be between low = Math.floor(bound / 2) and high = Math.min(bound, items.length - 1).
  5. Run a normal binary search from low to high and return what it finds.

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 exponentialSearch(items, target) {
  2. if (items.length === 0) return -1;
  3. let bound = 1;
  4. while (bound < items.length && items[bound] < target) {
  5. bound *= 2;
  6. }
  7. let low = Math.floor(bound / 2);
  8. let high = Math.min(bound, items.length - 1);
  9. while (low <= high) {
  10. const mid = Math.floor((low + high) / 2);
  11. if (items[mid] === target) return mid;
  12. if (items[mid] < target) {
  13. low = mid + 1;
  14. } else {
  15. high = mid - 1;
  16. }
  17. }
  18. return -1;
  19. }

How fast it is

TimeO(log i)
Extra memoryO(1)

i is the target's index. The doubling takes about log₂ i steps and the binary search about log₂ i more.

  • Best caseO(1)

    The target is at index 0 or 1: the doubling stops at once and the range has two items. Finding 1 at index 0 in the trace's list takes 2 reads.

  • Average caseO(log i)

    A target at index i costs about log₂ i doubling reads plus log₂ i binary search reads. For index 1,000 in a list of a billion numbers, that is 17 reads against 30 for plain binary search.

  • Worst caseO(log n)

    The target is near the end or missing: about 2 × log₂ n reads, 58 for a target near the end of a billion items, against 29 for plain binary search.

Common mistakes

  • Starting bound at 0. Doubling 0 gives 0 forever, so the loop never ends. Start at 1.
  • Forgetting Math.min(bound, items.length - 1). When bound ran past the end, high points outside the list.
  • Starting the binary search at 0 instead of bound / 2. It still works, but it throws away the speed-up for targets near the start.
  • Using it on an unsorted list. Like binary search, it silently gives wrong answers.

When to use it

Look for these clues in a problem:

  • The list is sorted but its length is unknown, or it is unbounded, like a stream or an endless feed.
  • The target is likely close to the start of a very long sorted list.
  • Reading far into the data is expensive, such as loading pages from a server, so you want to probe small indexes first.

Check yourself

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

Why does bound start at 1 and not 0?

Doubling 0 gives 0 forever, so the loop would never move. Index 0 is still covered, because the final range starts at Math.floor(1 / 2) = 0.

If the target is at index 100 of a long list, what is the last bound the doubling reaches?

128. The items at 1, 2, 4, ..., 64 are all smaller than the target, and 128 is the first power of two past 100.

Why can the final range start at bound / 2 instead of 0?

The previous doubling step read items[bound / 2] and found it smaller than the target, so it and everything before it are already ruled out.

When is exponential search slower than plain binary search?

When the length is known and the target is near the end. It spends about log₂ n reads doubling and then about log₂ n more inside the last range, close to twice as many.

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

While doubling, the loop keeps a promise: every item before index Math.floor(bound / 2) is smaller than target. At the start bound = 1, so that covers no items and is true. Each doubling happens only when items[bound] < target, and since the list is sorted, every item up to bound is smaller too. The new bound is twice the old one, so the promise holds for it.

The doubling stops either because bound is past the end or because items[bound] >= target. In the second case, if items[bound] equals the target it is inside the range, and if it is bigger, every later item is bigger too. Together with the promise, the target can only be from Math.floor(bound / 2) to Math.min(bound, items.length - 1).

The binary search then runs on a range that holds the target if it is anywhere, so its usual proof finishes the job. Both loops end: the doubling because bound passes the length after at most about log₂ n steps, and the binary search because its range shrinks with every check.

Going deeper

3 more ideas

Why the range is right

The doubling stopped because items[bound] was at least the target, or because bound ran past the end. The step before, items[bound / 2] was smaller than the target (or it was index 0). Since the list is sorted, the target can't be before bound / 2 or after bound. So the binary search range holds the target if it is anywhere.

How long it takes

If the target is at index i, the doubling stops after about log₂ i steps, and the binary search range has about i / 2 items, so it takes about log₂ i more steps. The total is O(log i). Since i is at most n, it is never worse than O(log n).

Galloping in real sorting code

TimSort, the sort used by V8 for Array.prototype.sort, uses the same idea while merging. When one run keeps winning, it stops comparing one item at a time and "gallops": it checks positions 1, 3, 7, 15... ahead to find how far it can jump, then binary searches that range and copies the whole block at once.

Work it by hand

Every step in a table, with why

Look for 50 in a sorted list of 13 numbers. It isn't there, and bound runs past the end, so the trace shows the clamp too.

items = [1, 3, 8, 10, 15, 22, 26, 31, 37, 44, 52, 60, 71], target = 50

StepPhasebound or rangemidItem readWhat happensWhy
1doublebound = 1-items[1] = 33 < 50, so bound = 2The first probe is index 1. 3 is smaller than the target, so keep doubling.
2doublebound = 2-items[2] = 88 < 50, so bound = 4Still smaller. Every item up to index 2 is now ruled out.
3doublebound = 4-items[4] = 1515 < 50, so bound = 8Still smaller. The jumps get bigger each time.
4doublebound = 8-items[8] = 3737 < 50, so bound = 16Still smaller, so everything up to index 8 is out.
5doublebound = 16-none16 < 13 is false: stopbound ran past the end of the 13-item list, so the doubling stops without reading anything.
6set uplow = 8, high = 12--high = Math.min(16, 12)The range starts at 16 / 2 = 8. Math.min pulls high back to the last index, 12, so the search never reads past the end.
7binary8 to 1210items[10] = 5252 > 50, so high = 9A normal binary search step on the small range.
8binary8 to 98items[8] = 3737 < 50, so low = 937 is too small, so move right.
9binary9 to 99items[9] = 4444 < 50, so low = 10One item is left, and it is too small too.
10binary10 to 9--low > high: stopThe range is empty, so 50 is not in the list.

It returns -1 after 7 item reads: 4 while doubling and 3 in the binary search. The target would have sat between 44 and 52, which is exactly where the range closed.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Exponential searchO(log i)O(1)The list has no known end, or the target is usually near the front.
Binary searchO(log n)O(1)You know the length and targets can be anywhere: its worst case needs about half the reads.
Linear search from the frontO(i)O(1)The target is almost always in the first few items, or the list isn't sorted.

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

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Exponential search and the other approaches, on a scale where each line up is 10 times more steps.
  • Exponential search, Binary search O(log i)
  • Linear search from the front O(i)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Exponential search31020
Binary search31020
Linear search from the front101,0001 million

Inputs that need care

6 tricky inputs
An empty list: items = []
The first line returns -1 right away, before any index is read.
One item: items = [7], target 7
bound = 1 is already past the end, so the doubling never runs. The range is 0 to Math.min(1, 0) = 0, and the binary search finds 7 at index 0.
A target at index 0: the trace's list, target 1
The doubling reads items[1] = 3, which is not smaller, so it stops. The range is 0 to 1, and the binary search finds 1 at mid = 0.
A target bigger than every item: the trace's list, target 90
The doubling runs until bound = 16 passes the end, then the binary search covers indexes 8 to 12 and returns -1. This is the slowest kind of input.
No known length: a function get(i) that returns Infinity past the end
Drop the bound < items.length check. An out-of-range read returns Infinity, which is never smaller than the target, so the doubling stops by itself. The binary search then reads through get too.
Copies of the target: [2, 5, 5, 5, 9], target 5
It returns whichever copy the binary search lands on. For the first copy, run a lower bound on the final range instead.

Variations and follow-ups

Twists interviewers add

Searching near a known spot

If the last answer was at index p and the next target is probably close, double outward from p: check p + 1, p + 2, p + 4, and so on. The cost is O(log d), where d is the distance from p. Scrolling through a sorted timeline often has this shape.

Lower bound inside the range

Swap the final binary search for a lower bound to get the first copy of the target, or the spot to insert it. The doubling phase doesn't change, because it only asks "is items[bound] smaller than the target?".

Bigger steps

You can grow bound by any factor, such as 4 instead of 2. That means fewer doubling reads but a wider final range. Doubling keeps the two phases balanced, so it is the usual choice.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "sorted array of unknown size", "infinite sorted stream", an interface like reader.get(i) that fails past the end, or "the target is likely near the start".
  • Explain it as two phases: "first find a range by doubling, then binary search inside it". Then say why the range is right: the previous bound was too small, and this one isn't.
  • Test by hand: a target at index 0, a target exactly at a power of two like index 4, a target past the end, and a list of one item.
  • The usual follow-up is "what is the time if the target is at index i?". Answer: O(log i), because both phases take about log₂ i steps. It is never worse than O(log n), and at most about twice plain binary search.

Where frontend code uses it

The same idea in real UI code
  • Searching an infinite-scroll feed sorted by time when the total count is unknown: probe pages 1, 2, 4, 8 until you pass the target time, then binary search the pages between.
  • V8's Array.prototype.sort is TimSort, which uses galloping (doubling, then binary search) when merging runs where one side keeps winning.
  • Looking up a recent version in a long sorted change log: most lookups are for recent entries near the front, so doubling from the front is fast.

Related algorithms