Binary Search Master Recap — All Patterns & Templates

Binary Search — Master Recap

Problems 301–345 | 45 posts | Easy × 8, Medium × 27, Hard × 10

The 7 Core Patterns

#	Pattern	When	lo/hi init
1	Classic Exact	sorted, find exact	0, n-1; lo<=hi
2	Left Boundary	first True position	0, n; lo<hi; hi=mid
3	Right Boundary	last True position	0, n; lo<hi; upper mid
4	Rotated Array	check which half sorted	0, n-1
5	BS on Answer	minimize/maximize feasible	answer range
6	2D Matrix	treat as 1D	0, m*n-1
7	Peak Finding	eliminate downhill	0, n-1; lo<hi

The Universal Template

# Left boundary (minimize) — first index where condition holds
lo, hi = lower_bound, upper_bound  # inclusive
while lo < hi:
    mid = lo + (hi - lo) // 2
    if condition(mid):
        hi = mid       # answer could be mid or left
    else:
        lo = mid + 1   # answer must be right of mid
return lo

# Right boundary (maximize) — last index where condition holds
lo, hi = lower_bound, upper_bound
while lo < hi:
    mid = lo + (hi - lo + 1) // 2  # upper mid prevents infinite loop
    if condition(mid):
        lo = mid       # answer could be mid or right
    else:
        hi = mid - 1   # answer must be left of mid
return lo

BS on Answer Cheatsheet

Problem	lo	hi	feasible(mid)	direction
Koko Eating	1	max(piles)	total_hours <= h	minimize: hi=mid
Ship Packages	max(w)	sum(w)	days_used <= d	minimize: hi=mid
Magnetic Force	1	(max-min)/(m-1)	count_with_gap >= m	maximize: lo=mid
Split Array	max(arr)	sum(arr)	parts <= k	minimize: hi=mid
Cutting Ribbons	1	max(r)	total_cuts >= k	maximize: lo=mid
Min Speed	1	1e7	total_time <= hour	minimize: hi=mid

Rotated Array Patterns

# Search target
if nums[lo] <= nums[mid]:  # left sorted
    if nums[lo] <= target < nums[mid]: hi=mid-1
    else: lo=mid+1
else:  # right sorted
    if nums[mid] < target <= nums[hi]: lo=mid+1
    else: hi=mid-1

# Find minimum
if nums[mid] > nums[hi]: lo=mid+1  # min in right
elif nums[mid] < nums[hi]: hi=mid  # min in left or mid
else: hi-=1  # duplicates: safe shrink

Big O Reference

Problem	Time	Space	Pattern
Classic Binary Search	O(log n)	O(1)	Classic
Find First/Last	O(log n)	O(1)	Left+Right boundary
Rotated Array	O(log n)	O(1)	Half-sort check
Koko Eating	O(n log m)	O(1)	BS on Answer
LIS Patience	O(n log n)	O(n)	Patience + bisect
Median Two Arrays	O(log min(m,n))	O(1)	Partition
Kth in Sorted Matrix	O(n log V)	O(1)	BS on Value
Count Range Sum	O(n log n)	O(n)	Merge Sort

Common Pitfalls

Overflow: use mid = lo + (hi-lo)//2, not (lo+hi)//2
Infinite loop: right-boundary template needs upper mid (lo+hi+1)//2
hi init: for insert position use hi = n (not n-1)
Rotated with dups: when nums[lo]==nums[mid], do lo++ (can't determine sorted half)
BS on Answer — feasible direction: minimize → if feasible: hi=mid; maximize → if feasible: lo=mid
Circular search: return letters[lo % n] to wrap around

MAANG Interview Priority

Must-Know:

Binary Search (classic + both boundaries)
Search in Rotated Array I & II
Find Minimum in Rotated Array
Koko Eating Bananas (BS on Answer)
LIS with patience sort
Median of Two Sorted Arrays

High Value:

Kth Smallest in Sorted Matrix
Split Array Largest Sum
Count of Range Sum (merge sort)
Russian Doll Envelopes (2D LIS)

Next Section → Trees (problems 346–420)