Skip to content
Back to AlgorithmsAll lessons

Algorithms

Binary Search on the Answer

O(log(range) · cost of the feasibility check) time — each guess halves the range of possible answers, the same as classic binary search, just spent on guesses instead of list positions.

The idea, in plain English

Normally, binary search hunts for a value sitting inside a sorted list. This trick reuses the same halving idea for a different job: guessing the answer to a problem, instead of a position in a list. Suppose you can quickly check whether a guess would work, and small guesses fail while big guesses succeed (or the other way around). Then you can binary search over the range of possible answers themselves, even though no actual list of answers exists anywhere.

How it works

  1. 1Work out the smallest and largest values the true answer could possibly be. That range is your search range.
  2. 2Try the middle guess in that range, and run a quick check for whether this guess works. This check must get easier to satisfy as the guess grows, or shrinks, in one consistent direction.
  3. 3If the guess works, it might be more than needed, so try smaller. If it fails, try bigger. Keep halving the range until it narrows down to the smallest guess that actually works.

When you'd use it

Use it for optimization problems that ask for a minimum or maximum value that satisfies some condition — the smallest ship capacity to deliver packages in time, the minimum speed to eat all your food before it runs out, or 'smallest X such that this check succeeds', whenever the check runs fast and the answers split cleanly into works and does not work.

Common beginner mistakes

  • Picking a check that is not consistently one-directional. Binary search on the answer only works if 'works' and 'does not work' split the range cleanly into two halves, with no flip-flopping back and forth.
  • Setting the initial search range too narrow and accidentally excluding the true answer. The lower bound must be a guess that could realistically still fail, and the upper bound one that is guaranteed to succeed.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Weights: 1 2 3 4 5 6 7 8 9 10
Days: 5
Minimum capacity: 15

See it in motion

Watch it guessBinary search on the answerShip in 4 daysO(log(range) · cost of the feasibility check) time — each guess halves the range of possible answers, the same as classic binary search, just spent on guesses instead of list positions.

Which is the smallest capacity to ship every package within 4 days? Binary-search the capacity itself.

10
Low
53
High
—
Guess
0
Tests
0.0s
Live rangeMidpoint guessEliminatedAnswer

Not sure this is the right topic? See the learning paths → or where this leads →