Binary search on the answer
When you can't search the input, search the possible answers. If checking one candidate is easy and the answers line up from "too small" to "big enough", binary search finds the smallest one that works.
The answers form a sorted list of no, no, no, yes, yes
A hungry animal eats from piles of bananas at a fixed speed, one pile at a time, and has 8 hours. What is the slowest speed that finishes in time? There is no list to search, and no formula. But two things are true:
- for any one speed, it is easy to check: add up the hours each pile takes;
- if a speed is fast enough, every faster speed is too.
So line up every possible speed, from 1 to the biggest pile. The checks read no, no, …, no, yes, yes, …, yes. Finding the first yes is exactly the lower-bound search from Linear & binary search, run over the candidate answers instead of over the input. That is binary search on the answer.
The rule
If a yes/no check on a candidate answer flips only once, from no to yes, binary search finds the first yes in O(log range) checks. The total cost is that number of checks times the cost of one check.
"Minimum that is enough" or "maximum that still works"
The slowest speed, smallest capacity or least time that still meets a deadline
Each value; can it finish in time?
Split a list into k parts making the largest part as small as possible
Each limit; does it need at most k parts?
The largest minimum distance when placing items
Each distance; can every item be placed that far apart?
Hints: a huge answer range (up to 10⁹) and a check that's easy to simulate
Searching beats trying every value
The slowest eating speed that finishes in time
The candidates are the speeds 1 to 11, the biggest pile. Each probe checks one speed by adding up the hours, rounding each pile up, since a pile that needs part of an hour still takes the whole hour.
Three checks instead of up to eleven. With piles up to a billion bananas, trying every speed is impossible; binary search needs about 30 checks.
The smallest ship that delivers in time
Packages must ship in their given order, a ship carries at most its capacity each day, and everything must arrive within 3 days. The candidates now start at the heaviest package (anything smaller can't carry it) and end at the total weight (one day is always enough). The check loads each day until the next package wouldn't fit.
Only the check changed between the two examples. That is the pattern: once you see the answers line up as no-then-yes, the search itself is always the same lower-bound loop.
Minimize the largest part
"As small as possible" over a huge space of ways to cut is the signal. Flip it: for a given limit, can the list be cut into at most k runs that each stay at or under it? Filling each run greedily until the next number would overflow answers that in one pass, and a bigger limit never needs more runs. So binary search the limit.
The shape to reuse
- 1lo ← the smallest possible answer
- 2hi ← the largest possible answer
- 3answer ← hi
- 4while lo ≤ hi
- 5 mid ← lo + floor((hi − lo) / 2)
- 6 if works(mid)
- 7 answer ← mid -- a yes: try smaller
- 8 hi ← mid − 1
- 9 else
- 10 lo ← mid + 1 -- a no: go bigger
- 11return answer
For "the largest value that still works", the checks read yes, yes, no, no: keep the last yes instead, moving lo up on a yes.
Where answer searches go wrong
If a faster speed could fail where a slower one worked, binary search can skip the answer. Convince yourself the checks are monotonic before searching.
The range must include the answer: the ship's lower bound is the heaviest package, not 1.
A pile of 7 at speed 3 takes 3 hours, not 2.33: use ceil, or the check says yes too early.
Totals of many large values can exceed fixed-size integers; stop adding once the total passes the limit.
3 questions
Remember this
- When the input can't be searched, search the possible answers: they line up as no, no, yes, yes.
- A lower-bound binary search finds the first yes in O(log range) checks; the cost is that many checks times one check.
- Make sure the check flips only once, and that the range really contains the answer.
Now solve some yourself
Only this topic 0 of 11 solved
- EasyWhole-number square root without a library
- EasyThe first bad version, with few checks
- MediumSmallest divisor that keeps a sum under a limit
- MediumLeast time for machines to make t products
- MediumFewest days until enough bouquets bloom
- MediumSplit a list into k parts with the smallest largest sum
- MediumLeast time for buses to make enough trips
- MediumFewest balls in the fullest bag after k splits
- MediumSpread products so the fullest store gets least
- MediumThe cap that brings a sum closest to a target
- MediumLargest equal pile each child can get
Mixed with topics you have practiced 0 unlocked
2 more once you have practiced Greedy algorithms, Basic sorting. Play one of its examples to the end and solve one of its problems to unlock them.
Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.
Next