0
Challenge · 32Sort & Search

Binary search on the answer

Patternsused in ~70% of apps

The moment binary search stops being about arrays. There is no sorted list anywhere in the problem. You binary search the range of possible answers, and it is one of the highest-leverage tricks in the whole course.

Core idea. When the answers form an ordered range and the property you want flips from false to true exactly once across it, you never have to try every answer. Guess the middle answer, ask a yes/no question about it, and throw away half the range.
Playground, this isn't a screenshot
candidate answers 1 … 10. "Is this big enough?"
1
no
2
no
3
no
4
no
5
no
6
yes
7
yes
8
yes
9
yes
10
yes
no no no no no | yes yes yes yes yes
One flip, in one direction. That is the entire requirement, and it is what lets you binary search for the boundary instead of trying all ten.

You are not searching data. You are searching the answer space, looking for the first "yes".

↑ play a little first, then dig in