Binary Search on the Answer
A book club has four chapters to read, of 30, 12, 25 and 8 pages, and six evenings to do it. The rule: each evening you read at most p pages, and only from one chapter, so a 25-page chapter at 10 pages an evening takes three evenings. What is the slowest pace that still finishes on time? There is no sorted list anywhere in sight, yet this is a binary search problem.
The rule
If "can it be done with x?" flips only once, binary search x.
Ask the yes-or-no question for every possible pace. A pace of 1 page an evening: no. A pace of 30: certainly yes. And once a pace works, every faster pace works too. So the answers, in order of pace, form a row that flips once from no to yes, and the slowest working pace is the first yes. That is the first_true template from the last lesson, searching over paces instead of positions:
def evenings_needed(chapters, pace):
return sum((pages + pace - 1) // pace for pages in chapters) # rounds up
def slowest_pace(chapters, evenings):
return first_true(1, max(chapters),
lambda pace: evenings_needed(chapters, pace) <= evenings)(pages + pace - 1) // pace divides and rounds up, because a half-used evening still counts as an evening. The search range runs from 1 to the longest chapter: at that pace every chapter takes one evening, and reading faster cannot help.
Each check costs one pass over the chapters, and there are about log₂ of the range checks. For 100,000 chapters and a longest chapter of a billion pages, that is about 30 passes instead of trying a billion paces.
The shortcut
The signal is a sentence shaped like "the smallest x such that something works" (or "the largest x such that it still works"). When you see it, you need only two things: a checker for one value of x, and bounds where the answer is certainly no and certainly yes.
Pace 15, the middle of 1 to 30
Evenings needed: 2 + 1 + 2 + 1 = 6. Yes, so 15 might be the answer:
hi = 15.
The trap is searching a question that does not flip just once. If a bigger x could sometimes fail again, the row is not no … yes … and binary search will confidently return a wrong answer. Always check that "works for x" means "works for everything beyond x".
Drills
Answer fast — trust the rule.
How many evenings does a pace of 10 pages need for chapters [30, 12, 25, 8]?
The club has only 4 evenings for chapters [30, 12, 25, 8]. What is the slowest pace that works?
Why is the longest chapter a safe upper bound for the pace?
Which problem suits binary search on the answer?
Remember
- If "can it be done with x?" flips only once, binary search x.
- Shortcut: "the smallest x such that it works" means a checker plus two bounds.
- Trap: a question that does not flip just once, which makes binary search wrong.