Topic Lesson
Learn Binary Search from scratch
A complete 4-step path: handwritten notebook primer, animated visualizer, speed check quiz, and compiler practice.
What is Binary Search
notebook noteBinary search is the guessing strategy used when searching a thick telephone directory or guessing a secret number between one and a hundred. Rather than inspecting names one by one from the first page, the search opens straight to the middle page. If the target precedes that middle entry, the entire back half is discarded; if it follows, the front half is eliminated. Repeating this halved split finds the item with remarkable speed.
When to reach for it
Reach for binary search when queries target sorted collections, rotated sorted arrays, or monotonic answer spaces. Strong hints include logarithmic time constraints like O(log n) or search ranges exceeding one billion where stepping one value at a time times out. It also applies when validating whether a guessed solution is possible via a monotonic boolean check, known as binary search on answer.
How to think about it
Define the search territory with two inclusive pointers, low and high. Compute the midpoint using low plus half the difference to high, avoiding integer overflow. Formulate an exact boolean condition that divides the range into true and false halves. Decide whether the boundary condition includes the midpoint or shifts strictly past it. The loop invariant states that the sought target, if it exists, remains trapped inside the interval throughout every iteration.
Operation costs
measured big-O| Operation | Time |
|---|---|
| find target in sorted array | O(log n) |
| find boundary in monotonic range | O(log n) |
Common mistakes to avoid
- Triggering integer overflow by computing middle using low plus high divided by two instead of low plus half of high minus low in fixed-width numeric types.
- Creating an infinite loop when the interval shrinks to two elements by setting low equal to mid when mid was rounded down.
- Mismatched loop condition and bounds updates, such as pairing low less than or equal to high with non-advancing pointer assignments that never terminate.