Binary search on the answer

Searching sorted data Mid-level Python 3.13+ Reviewed By Best Latest Apps

Pick the fix

Which question suits binary search on the answer?

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A The least daily capacity to finish all orders within 10 days

Right: more capacity never needs more days, and checking one capacity is a quick greedy pass.

A monotonic yes or no check over a range of values is what binary search on the answer needs.

Why not the others?
  • B The number of distinct values in a list. That is a set size, not a search.
  • C Whether a list contains a duplicate. A hash set answers that directly.

30-second answer

Instead of searching a list, search the range of possible answers. It works when you can check a candidate quickly and the check is monotonic: once a value works, every larger (or smaller) value works too. The search finds the boundary in O(log range) checks, each costing whatever the check costs.

Practise saying it · 45 s. No recording, just a timer

Explain binary search on the answer.

Say your answer out loud, then check which of these points you covered:

  • Search the value range
  • Monotonic check
  • Cost: log range × check

Deep dive

Signals: 'minimum capacity', 'smallest speed', 'largest minimum distance', 'least time to finish'.

The check is often a greedy pass, which makes the whole thing O(n log range).

Choose bounds that are obviously too small and obviously enough.

Common mistakes

  • Using it when the check is not monotonic.
  • Choosing an upper bound that might not work.

Senior take & follow-ups

Name the monotonic property out loud: 'if x works, x + 1 works'.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you handle real-valued answers?

    Show hint

    Loop a fixed number of times (say 60) or until hi - lo is below a tolerance.

  2. What about 'maximise the minimum'?

    Show hint

    Search for the largest value whose check passes; round mid up.

What each operation costs: Binary Search · Linear Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.