Binary Search
Beginner · 20 min read · Problem-Solving Patterns, Searching & Sorting
One bug-free template: find the first position where a condition becomes true.
Binary search is famous for being simple to describe and hard to get right. Off-by-one errors, infinite loops, < versus <=, mid versus mid + 1 — most people memorise three or four slightly different versions and mix them up under pressure.
The one idea: find the first true
Almost every binary search question can be phrased as: "Given a condition that is false, false, …, false, true, true, …, true across a range, find the first true."
Worked problems
"Last true" is always "first true of the opposite condition, minus one". You never need a second template.
Debugging checklist
Practice ladder
Interview questions
- How do you avoid infinite loops in binary search?
- What property must a problem have for binary search to apply?
Further reading
Key takeaways
- Phrase every binary search as "find the first index where a monotonic condition becomes true".
- One template: while (lo < hi) { mid = lo + (hi − lo) / 2; if (ok(mid)) hi = mid; else lo = mid + 1; }.
- Last true = (first true of the opposite condition) − 1.
- The search range can be any integer range, not just array indexes; use long for products.
- Rotated arrays: compare with the last element, or use "one half is always sorted".