Binary Search
Searching the answer instead of the input
The technique that makes binary search apply to problems with no sorted array anywhere in sight.
Key idea
The reframe
Some problems ask for the smallest value that makes something possible, or the largest that keeps something under a limit. There is no sorted array to search. There is, however, a range of candidate answers, and often a property over them that is monotone.
If a given answer works, every more generous answer also works. If it fails, every stricter answer also fails. That is the flip you need, and the search runs over the candidate answers rather than over the data.
The smallest example
Integer square root is the smallest useful case. There is no array at all; the candidates are the integers from 0 to n, and the property is that the square reaches n.
Why it works
The three things to write down
Every problem of this shape needs the same three decisions, and writing them down before coding is the difference between fifteen minutes and an hour.
First, the candidate range: what is the smallest answer that could conceivably work, and the largest that certainly does? Both bounds should be defensible in one sentence.
Second, the feasibility test: given a specific candidate, can I check whether it works, and what does that check cost? This is usually a simple loop over the input.
Third, the monotonicity argument: why does feasibility, once true, stay true for every larger candidate? If you cannot say why, the search is not valid.
A feasibility test with a loop inside it
Here the candidate is a capacity, and testing one requires walking the whole input. The total cost is the log of the candidate range times the cost of one test.
Tip
Where the bounds come from
The lower bound is the largest single load, because no capacity below that can ever carry it. The upper bound is the total, because one enormous batch always fits in a single day.
Both are stated in one sentence and both are provably safe. Guessing bounds such as 1 and a large constant usually still works and is a weaker answer, because a bound you cannot justify might be wrong on an input you have not thought about.
Cost
The cost of the whole thing
The search does about log of the range iterations, and each one runs the feasibility test. With a range up to the total and a linear test, that is O(n log(total)) overall.
Notice that the log is over the magnitude of the numbers, not the length of the array. That is normal for answer-space searches and is worth saying explicitly when you state the complexity, since it is a different quantity from the usual log n.
Gotcha
Check which way the property runs
Here a larger capacity is more generous, so feasibility flips from false to true as the candidate grows, and the template finds the smallest true.
Some problems run the other way, where a larger candidate is more demanding. Rather than rewriting the loop backward, define the property so it is false then true, even if that means phrasing it as an upper limit being respected. Keeping one loop shape and varying only the property is what stops this pattern from turning into four memorized templates.
Before the problem
Write the three decisions on paper: the candidate range with a justification for each bound, the feasibility test, and why feasibility is monotone. The problem below is straightforward once those exist and genuinely hard without them.
Feasibility tests
Answer-space searches live or die on the feasibility function, so write two of those and one search. groups_needed returns how many groups are needed if no group may exceed limit, splitting only between adjacent items. smallest_limit finds the smallest limit fitting within allowed groups. smallest_side returns the smallest integer side length whose square is at least area.
Tests
print(groups_needed([1, 2, 3, 4, 5], 5), groups_needed([1, 2, 3, 4, 5], 15)) print(smallest_limit([1, 2, 3, 4, 5], 2), smallest_limit([1, 2, 3, 4, 5], 5)) print(smallest_side(17), smallest_side(16), smallest_side(0))
Output
Run the tests when you are ready.
Koko Eating Bananas
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.