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.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
Playground, this isn't a screenshot
candidate answers 1 … 10. "Is this big enough?"
1
no2
no3
no4
no5
no6
yes7
yes8
yes9
yes10
yesno 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