Binary Search#
Also known as: Bisection, Half-Interval Search, Binary Search on the Answer
Halve the search space every step by asking one yes/no question. The array doesn't strictly need to be sorted — what it needs is a monotonic predicate: some property that's false, false, false, then true, true, true. Once you see that shape, you can binary search on it, even when the "array" is a range of possible answers rather than real data.
Before you start#
- Comfortable with basic array indexing and loop logic in your language.
What 'solved properly' looks like
Target: O(log n). If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea#
You look at the middle of your search space and ask one question. The answer tells you which half to discard — and you repeat until only the target remains. The key insight that separates mastery from competence is that this works on any monotonic predicate, not just sorted arrays: "find the smallest value such that f(x) is true" is a binary search even when there's no array at all.
Why it matters: Searching the answer space rather than the data is one of the biggest step-changes in problem-solving ability. Problems like "minimise the maximum" or "maximise the minimum" look nothing like a search, but the moment you recognise the monotonic shape, they collapse into a binary search with a simple check function.
When to reach for it#
Reach for it when the input is sorted and you need to find a target, when the array is rotated and you need to find a pivot, or — most importantly — when a problem asks you to "minimise the maximum" or "maximise the minimum" of something, and checking whether a candidate value works is much easier than computing the answer directly.
When not to use it
Off-by-one errors in the boundary update are the number-one bug. Pick a single template (inclusive or exclusive bounds) and never deviate. Compute the midpoint as low + (high - low) / 2 to avoid overflow in fixed-width languages. And critically: if the predicate isn't monotonic, binary search is simply invalid — verify that before you start.
Practice set#
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Binary Search | LeetCode | Easy | 15 mins | teaching |
| 2 | Search Insert Position | LeetCode | Easy | 15 mins | teaching |
| 3 | First Bad Version | LeetCode | Easy | 20 mins | consolidation |
| 4 | Find Minimum in Rotated Sorted Array | LeetCode | Medium | 25 mins | consolidation |
| 5 | Koko Eating Bananas | LeetCode | Medium | 35 mins | challenge |
Already know this? Test out.
If you can solve Koko Eating Bananas cleanly in one sitting — implementing the check function and the search loop correctly — you already own this pattern, so move on to the next one. If it tangles you up, that's your signal to work the set from the top instead of skipping.