Foundations
Binary Search
Cut the search space in half each step. Not just for sorted arrays - any monotonic signal works.
What is binary search?
Binary search exploits one property: if your search space is ordered (sorted, or has a clear yes/no boundary), you can test the midpoint and immediately discard half the space. Do that repeatedly and you reach the answer in O(log n) steps instead of O(n).
The classic version works on a sorted array - given a target, test the middle element. If the target is smaller, it must be in the left half; if larger, the right half. Each comparison halves the problem. On a million-element array, you find the answer in about 20 comparisons.
The deeper insight is that binary search works on any problem where there is a monotonic threshold - a line that cleanly separates "too small" from "good enough." This extends binary search far beyond arrays: minimum capacity problems, optimization problems, and geometry all use the same template.
Core operations
| Variant | Loop condition | hi update | Exit state |
|---|---|---|---|
| Exact match | lo <= hi | hi = mid - 1 | Returns -1 if not found |
| Leftmost bound | lo < hi | hi = mid | lo == hi is the answer |
| Rightmost bound | lo < hi | lo = mid + 1 | lo - 1 is the answer |
| Answer space | lo < hi | hi = mid or lo = mid + 1 | Depends on feasibility direction |
Key patterns
Exact match
The standard binary search: check the midpoint, then eliminate the half that cannot contain the target.
When to use - the input is sorted (or has a clear ordering) and you need to find a target value, its insertion point, or the first/last position where some condition holds. A linear scan costs O(n); exploiting the order drops that to O(log n).
How it works - keep two bounds, lo and hi, and look at the midpoint each step. If nums[mid] equals the target you are done; otherwise the order tells you which half to throw away, so you reset one bound past mid and repeat. The reason this is correct is the sorted order: everything left of a too-large mid is also too large, so discarding that half can never lose the target. The pieces must agree with each other. Plain exact match uses lo <= hi and hi = mid - 1, and the loop exits with lo > hi meaning the target is absent (return -1). The leftmost and rightmost variants use lo < hi and hi = mid (not mid - 1), because mid might itself be the answer you want to keep; they exit with lo == hi. Pair the wrong loop condition with the wrong hi update and you either skip the answer or loop forever.
Example: find the target in a sorted array. Given [1, 3, 5, 7, 9, 11, 13] and target 9, the first midpoint is index 3 (7 < 9), so the left half dies and lo jumps to 4. The next midpoint is index 5 (11 > 9), so hi drops to 4, and the third midpoint, index 4, holds exactly 9. Three comparisons to find index 4 in a seven-element array; the visualizer below follows each probe.
mid = lo + (hi - lo) // 2 not (lo + hi) // 2 - in languages with fixed-width integers, the sum can overflow. The subtraction form is safe and is the expected formula in an interview.Answer space
Binary search over a range of possible answer values rather than array indices, using a feasibility check in place of a direct comparison.
When to use - the problem asks for the minimum or maximum value such that something is possible ("smallest eating speed that finishes in time", "least capacity that ships in D days"). There is no array to index into, but the candidate answers form a range and a yes/no test splits it cleanly. Trying every candidate is O(n) over the value range; binary search makes it O(log n) tests.
How it works - the trick is that the feasibility check is monotonic: once a candidate value works, every larger value works too (or every smaller one, depending on direction). That single threshold is what lets you halve the range. Each step, test mid with the feasibility function and move the bound that keeps the threshold between lo and hi. The loop machinery has to stay consistent or the search breaks. Use lo < hi with hi = mid when mid could be the answer, and lo = mid + 1 when it cannot; the loop exits with lo == hi on the boundary value. Setting lo = mid instead of lo = mid + 1 is the classic bug - when lo + 1 == hi, mid == lo and lo never advances, so the loop spins forever.
Example: minimum eating speed (Koko). Piles [3, 6, 7, 11] must be finished within 8 hours, so the answer space is speeds 1 through 11 and each probe asks "is speed s fast enough?" The first midpoint, speed 6, finishes in 6 hours, so every faster speed is discarded at once and hi drops to 6. Speed 3 then needs 10 hours, too slow, so lo jumps past it; speed 5 and finally speed 4 each land exactly on 8 hours, and lo and hi meet on 4 - the slowest speed that still makes the deadline. The visualizer below tests each midpoint of the speed range.
hi = mid (not hi = mid - 1) in boundary-finding variants - when mid could still be the answer (leftmost occurrence, minimum feasible value), using hi = mid - 1 skips it. The rule: if mid is confirmed NOT the answer, use mid - 1; otherwise use mid.When to reach for binary search
- The input is sorted and you need to find a value or its insertion point - standard binary search.
- You see "minimum/maximum value such that X is possible" - binary search on the answer space.
- The problem has a clear yes/no threshold that doesn't flip back and forth - monotonic property.
- You need to find a peak element or the rotation point in a rotated sorted array.
- A brute-force O(n) scan feels too slow and the search space clearly has order - ask "can I binary search?"
Done reading? Mark it so it sticks in your dashboard.