cf.completefrontend
SEARCHING & BINARY SEARCH · CORE

Binary search on the answer

When the answer is a number and you can check whether a guess works, binary search over the possible answers.

Time O(n log R)Space O(1)11 practice problemsStep-through picture

The idea

Sometimes there is no sorted list to search at all. Instead the question is "what is the smallest speed that finishes on time?" or "what is the largest gap that still fits?". The answer is a number in some range, and you have a way to test a guess: "does speed 5 finish on time? yes or no".

If the test has a special shape, you can binary search the answer itself. The shape is: every guess below some point fails, and every guess from that point on works (or the other way around). Speed 3 is too slow, speed 4 is too slow, speed 5 works, speed 6 works, and so on. The answers form a sorted list of "no, no, no, yes, yes", and we want the first "yes".

Each test may take some work, like a loop over the input. But binary search needs only about 30 tests to search a range of a billion numbers, so the whole thing stays fast.

An everyday example

Picking the shortest ladder that reaches the roof

A hardware store has ladders from 1 to 20 meters, and you need the shortest one that reaches a roof. Trying every ladder from the shortest up is slow. Instead you try the 10-meter one. It reaches, so anything taller also reaches: the answer is 10 or less. You try 5 meters. Too short, so anything shorter is also too short. You try 7, then 8, halving the range every time, until one ladder is left.

How the example maps to the code
In the exampleIn the code
The range of ladder lengthslow and high
Trying a ladderworks(mid)
It reaches: try shorter ones, but keep this onehigh = mid
Too short: only taller ones can worklow = mid + 1
The one ladder leftreturn low

From the slow way to binary search on the answer

  1. Take the upload problem from the code: four files of sizes [5, 14, 8, 10] and 7 hours. The obvious way tries speed 1, then 2, then 3, and stops at the first speed that finishes in time. Each try loops over the files, so with speeds up to the largest file this costs n times the largest size, far too slow when sizes reach a billion.
  2. Notice a fact about the test: if speed s finishes in time, any faster speed also does, because each file takes the same number of hours or fewer. So the answers to "does speed s work?" for s = 1, 2, 3, ... look like false, false, ..., true, true. They form a sorted list of booleans, even though nobody writes that list down.
  3. On a sorted list you can binary search. Here the list is the range of speeds from low to high, and reading one item means calling works(mid). We want the first true, which is the lower bound pattern: when works(mid) is true, mid might be the answer, so keep it with high = mid; when it is false, low = mid + 1.
  4. Last, pick a range that surely holds the answer. Speed 1 is the smallest that makes sense. Speed Math.max(...files) works whenever any speed does, because every file then takes one hour, the fewest possible. A range, a yes-or-no test that flips once, and the lower bound loop over them: that loop is binary search on the answer.

How it works

  1. Decide the range of possible answers: the smallest value low that could work and the largest value high that surely works.
  2. Write works(guess), which returns true if the guess is good enough.
  3. While low < high, pick mid = Math.floor((low + high) / 2) and test it.
  4. If works(mid) is true, mid might be the answer, but something smaller might be too: set high = mid.
  5. If it is false, mid and everything smaller fail: set low = mid + 1.
  6. When low === high, that value is the smallest guess that works. Return it.

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 smallestThatWorks(low, high, works) {
  2. while (low < high) {
  3. const mid = Math.floor((low + high) / 2);
  4. if (works(mid)) {
  5. high = mid;
  6. } else {
  7. low = mid + 1;
  8. }
  9. }
  10. return low;
  11. }
  13. function minSpeed(files, hours) {
  14. const finishesInTime = (speed) => {
  15. let needed = 0;
  16. for (const size of files) needed += Math.ceil(size / speed);
  17. return needed <= hours;
  18. };
  19. return smallestThatWorks(1, Math.max(...files), finishesInTime);
  20. }

How fast it is

TimeO(n log R)
Extra memoryO(1)

R is the size of the answer range. Binary search makes about log₂ R guesses, and each test loops over the n items once.

  • Best caseO(n log R)

    Even when the answer is 1, the loop still makes about log₂ R tests, each a full pass over the n files, because it never stops early.

  • Average caseO(n log R)

    Any input: the answer range halves with each test, and each test costs one pass.

  • Worst caseO(n log R)

    About log₂ R tests of n steps each. With R near a billion and n = 100,000, that is about 30 passes, 3 million steps.

Common mistakes

  • Picking a range that does not contain the answer, such as starting low at 0 when a speed of 0 makes size / speed divide by zero. Think about the smallest and largest possible answers first.
  • Using a test that is not monotonic, meaning a bigger guess can fail after a smaller one worked. Then binary search gives wrong answers. Check that "bigger is never worse" really holds.
  • Using Math.floor(size / speed) instead of Math.ceil. A file of size 7 at speed 3 takes 3 hours, not 2.
  • Mixing the two directions: searching for the largest answer with mid rounded down and low = mid. The loop never ends when high = low + 1.

When to use it

Look for these clues in a problem:

  • The question asks for the minimum or maximum value that satisfies a condition: smallest capacity, largest distance, fewest days.
  • Checking one guess is easy, often a single loop, but computing the answer directly is hard.
  • If a guess works, every bigger guess also works (or every smaller one does).
  • The possible answers lie in a known range, such as 1 to max(items) or 0 to the sum of the items.

Check yourself

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

Why must the test be monotonic for this to work?

Binary search drops half the range after one test. That is only safe if a failing guess means every smaller guess fails too, and a passing guess means every bigger one passes.

Why is the top of the range Math.max(...files) and not something bigger?

At that speed every file takes exactly one hour, the fewest possible, so no faster speed can do better. A bigger high would still be correct, but it would add useless tests.

About how many tests does the search make when the answers range from 1 to 1,000,000?

About 20, because 2 to the 20th power is about a million.

What does the loop return if no speed in the range works?

It returns high, the top of the range, even though that speed fails. Check works(answer) afterwards, or rule out the impossible case before searching.

Practice problems

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

Not started

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

Start practicing

easy

medium

hard

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

Call the answer best: the smallest speed where the test is true. The loop keeps one promise: best is somewhere from low to high. At the start, low = 1 and high = Math.max(...files), and the promise holds as long as that top speed really works.

Each step keeps it. If works(mid) is true, then best <= mid, so high = mid keeps best in range. If it is false, then every speed up to mid also fails, because the test is monotonic (a slower speed never needs fewer hours), so best > mid, and low = mid + 1 is safe. mid is always less than high, so the range shrinks every time.

The loop ends when low === high, and by the promise that one value is best. Everything rests on the test being monotonic. If speed 6 could fail while speed 5 worked, the boolean list wouldn't be sorted, and one test would say nothing about its neighbors.

Going deeper

3 more ideas

Why the answers can be binary searched

Write down works(1), works(2), works(3), and so on. Because a bigger guess never makes things worse, the list looks like false, false, true, true, true. That list is sorted (all false before all true), and we want the first true. That is exactly a lower-bound search, only the list is never built: each item is computed when binary search asks for it.

How long it takes

If the range has R possible answers and one test costs O(n), the search costs O(n log R). For R up to a billion, log R is about 30, so it is about 30 passes over the input.

Searching for the largest answer that works

Some problems flip the shape: small guesses work and big ones fail, and you want the largest that works, like the biggest gap between items. Then true means "go right": if works(mid), set low = mid, else high = mid - 1. Pick mid = Math.floor((low + high + 1) / 2), rounding up, or the loop can get stuck when high = low + 1.

Work it by hand

Every step in a table, with why

Find the slowest upload speed that sends four files within 7 hours.

files = [5, 14, 8, 10], hours = 7

SteplowhighmidHours at speed midworks(mid)What happensWhy
111471 + 2 + 2 + 2 = 7true7 <= 7, so high = 7At speed 7 the files take 1, 2, 2, and 2 hours. That just fits, so 7 might be the answer, but a slower speed might fit too.
21742 + 4 + 2 + 3 = 11false11 > 7, so low = 5Speed 4 is too slow, and so is every speed below it. The answer is from 5 to 7.
35761 + 3 + 2 + 2 = 8false8 > 7, so low = 7Speed 6 misses by one hour, because the size-14 file still needs 3 hours.
477---low === high: return 7Only speed 7 is left, and the first test already showed that it works.

The answer is speed 7, found with 3 tests. Trying speeds from 1 upward would have needed 7 tests, and with sizes near a billion it would be about 30 tests against up to a billion.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Binary search on the answerO(n log R)O(1)The answer is a number in a big range, and you can test a guess with a monotonic yes-or-no check.
Try every answer from the smallestO(n · R)O(1)The range R is tiny, say a few hundred values, or the test isn't monotonic, so binary search would be wrong.
Binary search a sorted list of candidatesO(n log n)O(n)The answer must be one of n known values, such as one of the input numbers. Sort them and search that list with the same test, so the number of tests depends on n, not on how big the values are.

Extra memory: O(1) besides the input: the test keeps one running total, needed. One catch: Math.max(...files) passes every item as an argument, and in Node it throws a RangeError for arrays of around 125,000 items or more, so use a loop for big inputs.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Binary search on the answer and the other approaches, on a scale where each line up is 10 times more steps.
  • Binary search on the answer, Binary search a sorted list of candidates O(n log R)
  • Try every answer from the smallest O(n · R)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Binary search on the answer339,96620 million
Try every answer from the smallest1001 million1 trillion
Binary search a sorted list of candidates339,96620 million

Inputs that need care

5 tricky inputs
One file: files = [9], hours = 3
The range is 1 to 9, and the answer is 3, since Math.ceil(9 / 3) = 3. No special case is needed.
hours equals the number of files: [5, 14, 8, 10], hours = 4
Only a speed where every file takes one hour works, so the answer is 14, the top of the range. Every test fails until low reaches 14.
hours smaller than the number of files: same files, hours = 3
No speed can work, because each file takes at least one hour. The loop still returns 14, which is wrong. Check this case first, or test works(answer) before returning it.
Lots of time: same files, hours = 40
Every test passes, high keeps moving down, and the answer is 1, the bottom of the range.
Very large sizes, up to 10^9
R is a billion, so the search makes about 30 tests. The total needed can reach n × 10^9, which is still exact in a JavaScript number for any realistic n.

Variations and follow-ups

Twists interviewers add

Largest value that works

For questions like "the largest smallest gap between placed items", small guesses work and big ones fail, and you want the last true. Round mid up with Math.floor((low + high + 1) / 2), then set low = mid when it works and high = mid - 1 when it doesn't.

Real-number answers

When the answer is a real number, such as a font size or a ratio, loop a fixed number of times, say 60, with mid = (low + high) / 2, setting high = mid or low = mid. Each loop halves the range, so 60 loops shrink it by a factor of about 10^18.

Split into at most k groups

"Split the list into at most k runs of neighbors so the largest run's sum is as small as possible" has the same shape. Guess a cap mid, greedily count how many runs you need when no run may go over mid, and check that the count is at most k. A bigger cap never needs more runs, so the test is monotonic.

Expensive tests

The test doesn't have to be a simple loop. It can be a breadth-first search on a grid ("can we cross if the water level is mid?") or a measurement of rendered text. The total cost is always about log R tests times the cost of one test.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "minimum X such that...", "maximum X such that...", "smallest capacity", "fewest days", or "largest minimum distance", together with a large value range like up to 10^9.
  • Before coding, say three things: the range (low, high, and why high surely works), the test, and why the test is monotonic ("a faster speed never needs more hours"). The monotonic argument is what interviewers listen for.
  • Write the search and the test as two functions, like smallestThatWorks and finishesInTime. Then each can be checked alone: try the test on a couple of speeds by hand before running the search.
  • The usual follow-up is "what's the time complexity?". Answer O(n log R), where R is the size of the answer range, not of the input. Then point out that with R = 10^9 that is only about 30 passes.

Where frontend code uses it

The same idea in real UI code
  • Fitting a headline into a box: binary search the font size, and for each guess measure the text (for example with CanvasRenderingContext2D.measureText) to see if it fits. Many fit-text helpers work this way.
  • Truncating text with an ellipsis in the middle: binary search how many characters to keep, measuring each guess, instead of removing one character at a time.
  • Choosing a batch size so a list of uploads or API calls finishes within a time budget is the same "smallest value that works" search.

Related algorithms