Binary Search
Retrieval: spotting a hidden binary search
Two problems rebuilt cold, plus the signal that a problem wants a search over answers.
Key idea
Three signals
A sorted input and a question about position, count, or presence. That is the ordinary boundary search.
The words minimum, maximum, smallest, or largest attached to something that must satisfy a condition, with no sorted array anywhere. That is a search over the answer space, and the work is writing the feasibility test.
A constraint mentioning log time when the input is not sorted. That is a hint that some structure other than sortedness lets you discard a half, and finding that structure is the problem.
Tip
The question that settles it
For any candidate binary search, ask: if I test the middle candidate, does the result tell me which side to keep? If yes, write the loop. If no, the property is not monotone and no amount of fiddling with the bounds will fix it.
Is this a binary search?
You must find the smallest number of machines needed so that a batch of jobs finishes within a deadline, where more machines never make things slower. Does binary search apply, and over what?
Koko Eating Bananas, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.
Min Stack, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.