The binary search mental model
Binary search works on any **monotonic** function — not just sorted arrays. The core principle: if you can evaluate a yes/no condition at any point in a search space, and the answers are of the form "no, no, no, YES, YES, YES", you can binary search for the boundary in O(log n). The classic sorted array search is the simplest case: "is arr[mid] equal to target?" But the same logic applies to: "is this speed fast enough to ship all packages in D days?" "is this value a valid peak?" "can K workers finish in mid days?" Any monotonic condition can be binary searched.
Template 1 — Classic binary search
Find a target in a sorted array. Returns -1 if not found. ```python def binary_search(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 # avoids integer overflow if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1 ``` Key: `while left <= right` with `left = mid + 1` and `right = mid - 1`. This terminates because the search space strictly shrinks each iteration.
Template 2 — Find first/last occurrence (boundary finding)
Find the leftmost position where a condition becomes true. Canonical example: first occurrence of a target, or first position ≥ target. ```python def find_left_boundary(nums, target): left, right = 0, len(nums) # note: right = len(nums), not len-1 while left < right: # note: strict less than mid = left + (right - left) // 2 if nums[mid] < target: left = mid + 1 else: right = mid # note: right = mid, not mid - 1 return left # left == right, first position where nums[left] >= target ``` For rightmost occurrence: use `nums[mid] <= target → left = mid + 1`, else `right = mid`, return `left - 1`. Problems: Find First and Last Position (LC 34), Search Insert Position (LC 35).
Template 3 — Rotated sorted array
A sorted array is rotated at an unknown pivot. Strategy: one half is always sorted — identify which half and check if the target is in that range. ```python def search_rotated(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid # Left half is sorted if nums[left] <= nums[mid]: if nums[left] <= target < nums[mid]: right = mid - 1 else: left = mid + 1 # Right half is sorted else: if nums[mid] < target <= nums[right]: left = mid + 1 else: right = mid - 1 return -1 ``` Problems: Search in Rotated Sorted Array (LC 33), Find Minimum in Rotated Sorted Array (LC 153).
Template 4 — Binary search on answer (most powerful)
The search space is not an array — it is a range of possible answers. You define a condition check function and binary search for the minimum (or maximum) valid answer. **Pattern:** ```python def solve(params): def condition(value) -> bool: # Returns True if `value` is a valid answer # Must be monotonic: all False ... then all True pass left, right = min_possible_answer, max_possible_answer while left < right: mid = left + (right - left) // 2 if condition(mid): right = mid # try smaller else: left = mid + 1 # too small, try larger return left ``` **Koko Eating Bananas (LC 875) — worked example:** ```python def minEatingSpeed(piles, h): def canFinish(speed): return sum((pile - 1) // speed + 1 for pile in piles) <= h left, right = 1, max(piles) while left < right: mid = left + (right - left) // 2 if canFinish(mid): right = mid else: left = mid + 1 return left ``` **Problems using this template:** Koko Eating Bananas (LC 875), Minimum Number of Days to Make m Bouquets (LC 1482), Capacity to Ship Packages (LC 1011), Split Array Largest Sum (LC 410), Minimize Maximum Distance to Gas Stations (LC 774).
Recognizing binary search problems
The signal that a problem wants binary search is often hidden. Ask yourself: 1. **Is the data sorted?** → Classic binary search or rotated array variant. 2. **Does the problem ask for a minimum/maximum value satisfying a constraint?** → Binary search on answer. 3. **Is there a monotonic yes/no function over a continuous range?** → Binary search on answer. 4. **Does a brute force of O(n²) or O(n log n) come to mind, but the constraint is n ≤ 10⁹?** → The answer space suggests binary search + a linear/log check function. Keywords: "minimum speed such that", "maximum number of", "feasible in D days", "smallest valid value", "split array into k parts to minimize maximum". Time complexity: binary search itself is O(log n). Total complexity = O(log(answer_range) × cost_of_condition_check). For Koko: O(log(max_pile) × n) where n is the number of piles.