Binary Search
Every comparison throws away half of what's left. Twenty questions beats a million.
5 lessons · ~49 min · free
By the end you can
- Feel why halving turns a million elements into twenty comparisons
- Write the classic template and know exactly why the loop terminates
- Find boundaries: first occurrence, last occurrence, lower and upper bound
- Search the answer space when there is no array at all
- Recognize monotonic structure, the real prerequisite for binary search
Lessons
- 1The power of throwing half away8 minThe guessing game, log₂ growth, and what sorted order actually buys you.
- 2The classic template11 minlo, hi, mid, and the loop condition, plus the two bugs that cause infinite loops.
- 3Boundaries: first and last11 minFirst occurrence, last occurrence, and the first-true picture that unifies them.
- 4Searching the answer space11 minNo array, no problem: binary search over candidate answers with a yes/no check.
- 5Spotting binary search problems8 minMonotonic structure in disguise, rotated arrays, and when halving simply doesn't apply.
Practice it after
Real interview questions that test this pattern, in an editor with execution and AI feedback.