Binary Search
Binary search halves the search space each iteration by comparing the midpoint to the target, achieving O(log n) on sorted arrays.
Binary search = the 'guess the number' game. 'Higher or lower?' Rip the phone book in half each time. You never re-read pages you already eliminated.
Template: lo=0, hi=n-1. While lo <= hi: mid = lo + (hi-lo)//2. If target found return mid. If arr[mid] < target: lo = mid+1 else hi = mid-1. For left boundary (first occurrence): use lo < hi, hi = mid when arr[mid] >= target. For right boundary: lo = mid+1 when arr[mid] <= target. Key extension: binary search on the answer space (not an array) — 'what is the minimum capacity such that condition holds?' Apply binary search to the answer range.
The standard template with lo <= hi finds exact matches. Left-boundary template (lo < hi, hi=mid) finds the first position where arr[mid] >= target — useful for lower_bound. Right-boundary finds last position. When binary searching on an answer (e.g., minimum days to ship packages), define a monotonic predicate: 'canShipInDDays(capacity)' is False up to a threshold, then True beyond — binary search on the threshold. mid = lo + (hi-lo)//2 prevents integer overflow vs (lo+hi)//2 — critical in Java/C++, not Python (arbitrary integers).
I reach for binary search in three scenarios: (1) searching a sorted array for a target or boundary; (2) binary searching on the answer space when I can check a condition in O(n) and the answer space is monotonic; (3) finding the rotation point or peak in a rotated/mountain array. For left/right boundaries I use a variant where I never return from inside the loop — just narrow until lo == hi. I always verify with a 2-element array to check my termination condition.
Using lo <= hi for boundary search causes infinite loops when lo = hi and the condition sets hi = mid (since mid = lo = hi). Use lo < hi for boundary searches. The classic off-by-one: if you set hi = mid-1 when you should set hi = mid, you skip the answer. Always mentally trace a 2-element and 1-element case.