Topic 6 of 20
Halve the search space each step, on arrays and, more powerfully, on the answer itself.
Binary search finds a target in a sorted range by repeatedly discarding half of it, giving O(log n) time. It sounds simple, but off-by-one errors make it one of the most commonly failed interview topics. Pick one template (for example lo < hi with hi = mid or lo = mid + 1), learn exactly what it returns (the first index where a condition becomes true), and use it every time.
The real power of binary search is that it works on any monotonic condition, not just sorted arrays. If "can we finish with speed x?" is false for small x and true for large x, you can binary search on x itself. This binary search on the answer pattern solves a large family of "minimise the maximum" and "find the smallest capacity" questions in O(n log range).
You will also meet rotated arrays (one half is always sorted, so decide which half to keep), 2D matrices treated as 1D, and the famous median-of-two-sorted-arrays partition trick.
Nail one bug-free template before anything else.
Lower bound: the first index whose value is ≥ target.
Binary search over a boolean predicate, the foundation of search-on-answer.
Searching over the answer space instead of an array.
An interactive-API variant that forces careful boundary updates.
Lower and upper bound together; very frequently asked.
Treat a matrix as a flattened sorted array.
Start at a corner and eliminate a row or column per step.
Minimise a capacity subject to a feasibility check.
Search on days, checking contiguous groups.
Sort once, then binary search per query.
Compare with the right end to find the pivot.
Decide which half is sorted; one of the most-asked Mediums.
Binary search without sorted data, guided by the slope.
Uses index parity to decide which side is broken.
A design question whose core is upper-bound search.
Binary search for the left edge of the best window.
Counting elements ≤ mid across a sorted matrix.
The famous O(log(min(m,n))) partition problem.
Minimise the maximum subarray sum; a classic Hard.
Composes three binary searches under an API-call limit.
Counting under a formula without building the table.
Combines search on answer with a two-pointer count.