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.