Binary Search
Eliminate half the search space every single step. The pattern that turns O(n) brute force into O(log n) — and appears in disguise across dozens of problems.
1,000,000 names — 1,000,000 checks vs 20 checks
A phone book has 1,000,000 sorted names. Linear scan: check every name one by one. Binary search: flip to the middle, throw away half, repeat. Each step eliminates half the remaining candidates.
Real-World Analogies
Real-world intuition before touching code.
Flip to middle. Too early → go right. Too late → go left. You never read every page.
"1–100. Guess." You say 50. "Higher." You say 75. Found in 7 guesses, not 100.
Looking up 'quarrel'. Open to 'M'. Too early. Each open halves remaining pages.
Core Intuition
The one thing that must be true for binary search to work.
Binary search requires one thing: a monotonic condition. The property you're searching on must change direction exactly once — False to True, or True to False — and never flip back. When that holds, you can look at the midpoint and say: "the answer is definitely not in that half." You throw it away forever.
Pattern Recognition
See these → reach for Binary Search immediately.