Pattern 11: Modified Binary Search

Deep Dive: Binary Search Beyond Sorted Arrays

Search Space = Range of Possible Answers

Koko Eating Bananas: piles=[30,11,23,4,20], hours=5

lo=1   hi=30  mid=15  hours_needed(15)=2+1+2+1+2=8 > 5  -> too slow, lo=16
lo=16  hi=30  mid=23  hours_needed(23)=2+1+1+1+1=6 > 5  -> lo=24
lo=24  hi=30  mid=27  hours_needed(27)=2+1+1+1+1=6 > 5  -> lo=28
lo=28  hi=30  mid=29  hours_needed(29)=2+1+1+1+1=6 > 5  -> lo=30
lo=30  hi=30  -> answer: 30

Wait, that seems high. Let me recheck: hours_needed(23)=ceil(30/23)+...=2+1+1+1+1=6. 
hours_needed(30)=1+1+1+1+1=5 <=5. Answer=30.

The pattern: Define can_do(x) returning True/False. Binary search for the smallest x where can_do(x) is True. Works whenever the predicate is monotonic (once True, stays True for all larger x).

---

Signal: Sorted (possibly rotated) data, "minimum/maximum satisfying condition", "search space with monotonic property" Template: binary_search() in templates.py

When to Use

• Classic sorted array search
• Rotated sorted array (find min, search for target)
• "Binary search on answer" -- minimum X such that condition holds
• Any problem with a monotonic predicate

Re-solve from Phase 1-2 (TIMED)

Problem	Source	Target Time	Done?
Search in Rotated Sorted Array	Phase 2.1	15 min	[ ]
Koko Eating Bananas	Phase 2.1	20 min	[ ]
Time Based Key-Value Store	Phase 2.1	20 min	[ ]

New Practice Problems

Add problems to solutions/ and enrich as needed.

---

First-time Recognition Signals

When you read a brand-new problem statement, this pattern is the right tool if you see:

• "Sorted array (possibly rotated, possibly with duplicates), find / locate X" — classic binary search, with care at the rotation pivot.
• "Find the smallest / largest value such that a predicate is True" with a monotonic predicate — binary search on the answer.
• "Minimise the maximum X" or "Maximise the minimum Y" — the giveaway phrasing for binary-search-on-answer (Koko Eating Bananas, Ship Packages in D Days, Split Array Largest Sum).
• "Answer space is huge (1 ≤ ans ≤ 10^9) but you can cheaply test a candidate answer" — O(n log answer_range) is feasible.
• "Find the peak element / first bad version / boundary in a monotone region" — log-time search over an implicit ordering.

Anti-signals (looks like this pattern, isn't)

• "Find the kth largest element" in an unsorted array — Heap or Quickselect is the natural tool, not binary search.
• "Search a 2D grid where rows and columns are sorted independently" — staircase search from the top-right corner runs in O(m+n), beating binary search.
• "The predicate is non-monotonic" (True / False / True / False over the search space) — binary search will silently return wrong answers; the problem needs a different decomposition.