Binary Search

O(log n) search over any monotonic search space — it doesn't have to be a literal sorted array. The template narrows a lo/hi range each iteration based on a condition at mid; the classic bug zone is the boundary update (lo = mid + 1 vs. hi = mid), worth tracing carefully rather than guessing.

Sub-patterns

• A — Search in a Sorted Array. The textbook case.
• B — Search in a Rotated Sorted Array. Figure out which half is still sorted, then decide which half to search.
• C — Search for a Boundary. First/last occurrence — narrowing toward an edge instead of an exact match.
• D — Binary Search on the Answer Space. Minimize or maximize a feasible value rather than searching an array directly.
• E — Search in a 2D Matrix. Treat sorted rows/columns as one flattened or nested binary search.

Practice set (15)

• Easy — Binary Search, Search Insert Position, First Bad Version, Sqrt(x)
• Medium — Search in Rotated Sorted Array, Find First and Last Position of Element in Sorted Array, Search a 2D Matrix, Find Minimum in Rotated Sorted Array, Koko Eating Bananas, Search in Rotated Sorted Array II, Find Peak Element, Capacity To Ship Packages Within D Days
• Hard — Median of Two Sorted Arrays, Split Array Largest Sum, Find in Mountain Array