Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Binary Search on the Answer

Binary search on the answer guesses a number, tests it with a yes-or-no check and halves the range of guesses. Two templates, worked examples and pitfalls.

Binary search on the answer finds the smallest (or largest) number that passes a yes-or-no test by guessing a number in the middle of the possible answers, testing it, and throwing away the half that can no longer hold the answer. There is no sorted array to look through: the thing being searched is the range of answers itself.

The idea

Imagine setting the speed of a conveyor belt in a factory. Too slow and the day's orders are not finished by closing time. Fast enough and they are. Any speed above "fast enough" also works. You want the slowest speed that still finishes on time.

You could try speed 1, then 2, then 3, until one works. Or you could try a speed in the middle of the dial. If it finishes on time, every faster speed does too, so only the slower half is still interesting. If it does not, every slower speed fails as well, so only the faster half is. One test removes half the dial.

That is ordinary binary search, with two changes:

  • The "array" is the list of candidate answers, such as every speed from 1 to 500. It is never built; only its two ends are stored.
  • The comparison with the middle item is replaced by a test function that says whether a candidate is good enough.

Line the candidates up and write the test result under each one. The method works only when the results look like this, with a single switch from one answer to the other:

candidate:  1   2   3   4   5   6   7   8   9
passes?     no  no  no  no  yes yes yes yes yes
                            ↑
                  the smallest candidate that passes

This property is called being monotonic: once the test starts passing, it never goes back to failing. Binary search finds the switching point.

When to use it

  • The question asks for the smallest or largest number that satisfies a condition: the lowest speed, the least capacity, the shortest time, the longest length.
  • Checking one candidate is much easier than finding the best one directly. "Can it be done at speed 7?" is a single pass through the data.
  • The test is monotonic: if a candidate passes, so does every larger one (or every smaller one).
  • The answer lies in a known range of whole numbers, even a very wide one.
  • A common wording is "make the largest thing as small as possible" or "make the smallest thing as large as possible".

Three decisions

Every problem of this kind is solved by settling the same three things.

  1. The range. What is the smallest value the answer could be, and what is the largest? Both ends must be safe: the answer must not lie outside them.
  2. The test. A function that takes one candidate and returns true or false. It usually loops over the input once.
  3. The direction. Are you after the first candidate that passes (failures on the left, passes on the right) or the last one that passes (passes on the left, failures on the right)?

The direction picks the template.

Template 1: the smallest value that passes

Use this when small candidates fail and large ones pass.

// The smallest whole number from lo to hi for which passes(x) is true.
// hi itself must pass.
function smallestPassing(lo, hi, passes) {
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);   // rounded down
 
    if (passes(mid)) {
      hi = mid;        // mid works: the answer is mid or something smaller
    } else {
      lo = mid + 1;    // mid fails: the answer is larger
    }
  }
  return lo;
}

When the test passes, mid stays in the range because it may be the answer. When it fails, mid is ruled out. The loop ends when one candidate is left.

Worked example: the print room

A print room has several printers. Printer i needs printers[i] minutes for each copy, and all of them run at once. What is the smallest number of minutes in which the room can produce at least copies copies?

  • Range. At least 1 minute. At most, the fastest printer does the whole job alone: Math.min(...printers) * copies minutes.
  • Test. In minutes minutes, a printer finishes Math.floor(minutes / printers[i]) copies. Add these up and compare with copies.
  • Direction. More minutes never produce fewer copies, so the test goes from failing to passing: the smallest passing value is wanted.
function copiesMadeIn(printers, minutes) {
  let total = 0;
  for (const minutesPerCopy of printers) {
    total += Math.floor(minutes / minutesPerCopy);
  }
  return total;
}
 
function minMinutesToPrint(printers, copies) {
  let lo = 1;
  let hi = Math.min(...printers) * copies;
 
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
 
    if (copiesMadeIn(printers, mid) >= copies) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }
  return lo;
}

minMinutesToPrint([2, 3, 7], 10) starts with the range 1 to 20:

lo hi mid Copies made in mid minutes Enough? Action
1 20 10 5 + 3 + 1 = 9 No lo = 11
11 20 15 7 + 5 + 2 = 14 Yes hi = 15
11 15 13 6 + 4 + 1 = 11 Yes hi = 13
11 13 12 6 + 4 + 1 = 11 Yes hi = 12
11 12 11 5 + 3 + 1 = 9 No lo = 12
12 12 Return 12

Five tests instead of twelve. With a range of a thousand million minutes it would be about thirty tests instead of a thousand million.

Template 2: the largest value that passes

Use this when small candidates pass and large ones fail.

// The largest whole number from lo to hi for which passes(x) is true.
// lo itself must pass.
function largestPassing(lo, hi, passes) {
  while (lo < hi) {
    const mid = lo + Math.ceil((hi - lo) / 2);    // rounded UP
 
    if (passes(mid)) {
      lo = mid;        // mid works: the answer is mid or something larger
    } else {
      hi = mid - 1;    // mid fails: the answer is smaller
    }
  }
  return lo;
}

The middle is rounded up here. With two candidates left, a middle rounded down equals lo, and lo = mid would then change nothing: the loop would never end. The rule from the binary search pattern applies: hi = mid goes with rounding down, lo = mid goes with rounding up.

Worked example: cutting ribbons

You have some ribbons of various lengths and need at least pieces pieces, all of the same whole-number length. Ribbons can be cut but not joined. What is the longest piece length that works? Return 0 if even pieces of length 1 are too few.

  • Range. From 0 (meaning "impossible") to the longest ribbon.
  • Test. A ribbon of length r gives Math.floor(r / length) pieces. Add them up.
  • Direction. Shorter pieces never give fewer of them, so the test goes from passing to failing: the largest passing value is wanted.
function maxRibbonLength(ribbons, pieces) {
  let lo = 0;                       // 0 always "passes": it is the fallback answer
  let hi = Math.max(...ribbons);
 
  while (lo < hi) {
    const mid = lo + Math.ceil((hi - lo) / 2);
 
    let count = 0;
    for (const ribbon of ribbons) count += Math.floor(ribbon / mid);
 
    if (count >= pieces) {
      lo = mid;
    } else {
      hi = mid - 1;
    }
  }
  return lo;
}

Because the middle is rounded up, mid is never 0 and the division is safe. maxRibbonLength([9, 7, 5], 4):

lo hi mid Pieces of length mid Enough? Action
0 9 5 1 + 1 + 1 = 3 No hi = 4
0 4 2 4 + 3 + 2 = 9 Yes lo = 2
2 4 3 3 + 2 + 1 = 6 Yes lo = 3
3 4 4 2 + 1 + 1 = 4 Yes lo = 4
4 4 Return 4

Checking that the test is monotonic

Before writing any code, say the reason out loud in one sentence:

  • "If the room can print the copies in 12 minutes, it can in 13."
  • "If pieces of length 4 are enough, pieces of length 3 are too."

If you cannot finish the sentence, the method does not apply. "Is there a pair of numbers that adds up to exactly x?" is not monotonic: it may be true for 10, false for 11 and true again for 12. Halving the range would throw away real answers.

Choosing the two ends

The ends should be as tight as you can easily justify, but being generous costs almost nothing: making the range a thousand times wider adds only ten steps. What matters is that they are safe.

Looking for Low end High end
Smallest speed or rate 1 (0 would divide by zero) The value that finishes in the shortest time allowed
Smallest capacity for items that cannot be broken up The largest single item The sum of all items
Smallest time 0 or 1 The time the slowest sensible plan takes
Largest length or count 0 or 1, a value known to pass The largest value in the input

Variations

Problem Candidate answer Test Example
Largest value under a limit A count A formula, no loop needed Arranging Coins
Slowest rate that meets a deadline A speed Add up the time each item takes Koko Eating Bananas
Make the largest part as small as possible A limit on each part Fill parts greedily and count them Split Array Largest Sum
Answer is a fraction A real number The same kind of test Loop a fixed number of times, such as 60, instead of until the ends meet

Complexity

  • Time: O(T × log R), where R is the number of candidate answers and T is the cost of one test. With a test that loops over n items once, that is O(n log R).
  • Space: O(1) beyond what the test itself uses.

Note that R is a range of values, not the length of the input. Searching speeds from 1 to 1,000,000,000 takes about 30 tests however short the input is. Why halving gives a logarithm is covered in Big O notation explained.

Common mistakes

  • Using it when the test is not monotonic. The code runs and returns something, but it is not the answer.
  • An unsafe range. If the true answer is larger than hi, the search can only return hi, which is wrong. Starting a speed at 0 leads to division by zero.
  • Rounding the middle the wrong way. lo = mid with a rounded-down middle loops for ever on a range of two.
  • An off-by-one in the test. >= against > in the test moves the answer by one. Try the test by hand on the expected answer and on its neighbour.
  • Returning the wrong thing. The loop ends with the best candidate. Some questions want that candidate, others want a value calculated from it.
  • Sorting the input for no reason. The input does not have to be sorted. Only the candidates are in order, and they always are: they are consecutive whole numbers.
  • Overflow in other languages. Sums and products inside the test can exceed a 32-bit integer in Java or C++. Use a 64-bit type there.

Practise

  1. Arranging Coins (easy): the largest passing value, with a formula as the test.
  2. Koko Eating Bananas (medium): the smallest passing speed.
  3. Split Array Largest Sum (hard): a greedy test inside the search.

Practice problems

ProblemDifficultyTimeSpaceRead
Arranging CoinseasyO(log n)O(1)Medium read: 7 min
Koko Eating BananasmediumO(n log m)O(1)Medium read: 8 min
Split Array Largest SumhardO(n log S)O(1)Long read: 11 min