Coding Prep
Binary Search
Halving the search space - how binary search achieves O(log n), how to get the boundary conditions right, and how to apply the same idea beyond sorted arrays to any problem with a monotonic feasibility check.
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.
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.
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.Canonical examples
Three patterns in one block
Three patterns in one block: standard exact-match, leftmost-occurrence boundary search, and binary search on the answer space. The minimum eating speed problem is the canonical answer-space template - the feasibility check tests whether a given speed allows finishing all piles in time.
lo = mid - when lo + 1 == hi, mid == lo. Setting lo = mid leaves lo unchanged forever. Always advance the left pointer with lo = mid + 1.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?"
Practice problems
- Search Insert Position - Leftmost boundary variant; the simplest problem to nail the boundary conditions.
- Find Minimum in Rotated Sorted Array - Inflection point detection.
- Koko Eating Bananas - Answer-space binary search, the template problem.
- Search in Rotated Sorted Array - Combining rotation detection with standard binary search.
Challenges that exercise this
Practical multi-level challenges that put this primer to work.
Done reading? Mark it so it sticks in your dashboard.