Divide-and-Conquer | Sorted Arrays | O(log n)
Imagine looking up "zebra" in a paper dictionary. You don't start at "aardvark" and read every word — you flip near the back, see you've gone a little too far, and jump into the half that's left. Then you split that half, and again, until you land on the word. Binary search is exactly this trick applied to a sorted list: look in the middle, throw away the half that can't contain your target, and repeat.
The list has to be sorted first — that is the one rule. We keep three markers: lo (the low end of what's still possible), hi (the high end), and mid (the middle between them). Each step we compare the target with the value sitting at mid. If they match, we're done. If the target is larger, it can only be in the right half, so lo jumps to mid+1. If it's smaller, it's in the left half, so hi drops to mid−1. Every single comparison throws away half of what's left. Starting from n items, one step leaves n/2, two steps leave n/4, and so on. A sorted list of 1,000 names shrinks 500, 250, 125, 63, 32, 16, 8, 4, 2, 1 — just 10 comparisons to find anyone, instead of up to 1,000 if you checked them one by one.
How many halvings does it take to shrink n all the way down to 1? That's the question $n/2^k \lt 1$, which rearranges to $k \gt \log_2 n$. So binary search runs in $O(\log n)$ time, captured by the recurrence $T(n) = T(n/2) + 1$: doubling the amount of data adds only one extra comparison. A billion sorted items need about 30 steps. In the simulation above, the Array Size slider sets n, the Target box (or a preset) sets what you're hunting for, and the lo / mid / hi cards show the search window collapsing in real time.
| Symbol | Meaning |
|---|---|
| n | Array size |
| T(n) | Max comparisons for array of size n |
| ⌊log₂n⌋ | Floor of log base 2 of n |
❌ "Binary Search works on unsorted arrays."
✅ Binary Search requires sorted data. On unsorted data, eliminating a half-array is incorrect — the target could be anywhere.
❌ "Binary Search always checks exactly log₂n elements."
✅ log₂n is the upper bound. If the target is at the first mid position checked, it terminates in 1 step (best case O(1)).
❌ "Binary Search is always better than linear search."
✅ For very small arrays (n ≤ 8), linear search is faster due to branch prediction and no overhead. For nearly-sorted small arrays, linear scan is competitive.
❌ Using mid = (lo+hi)/2 (potential integer overflow).
✅ Use mid = lo + (hi-lo)/2 or (lo+hi) >>> 1 (unsigned right shift in Java).
❌ Loop condition while (lo < hi) instead of while (lo <= hi) for exact match search.
✅ lo < hi exits when lo==hi without checking that last element. Use lo <= hi for exact match. For lower_bound/upper_bound, lo < hi is correct with different return logic.
❌ Infinite loop: forgetting to update lo or hi after mid doesn't match.
✅ Always: lo = mid+1 (right move) or hi = mid-1 (left move). Setting lo = mid or hi = mid without adjusting can loop forever when lo == hi == mid.