The Most Elegant Algorithm
Binary search is the simplest and most powerful example of the divide-and-conquer strategy. Given a sorted array and a target value, it checks the middle element and discards half the array with each comparison. This means searching through a million elements takes at most 20 steps. Jon Bentley famously noted that despite its simplicity, most programmers can't write a correct binary search implementation — off-by-one errors are notoriously tricky.
Logarithmic vs Linear
The difference between O(log n) and O(n) is the difference between practical and impractical at scale. A phone book with 1 million names: binary search finds any name in 20 comparisons. Linear search might need all 1 million. A database with 1 billion records: binary search needs 30 steps. Linear search needs up to 1 billion. Every doubling of data adds just one more step to binary search.
Watching the Race
The simulation shows two copies of a sorted array. The linear search (red) checks elements one by one from the left. The binary search (cyan) jumps to the middle, then halves its range. Watch how the binary search's remaining range (shown as a highlighted band) shrinks exponentially while the linear search crawls forward. The step counters make the difference viscerally clear.
Beyond Simple Arrays
The binary search principle extends far beyond arrays. Binary search trees organize data for O(log n) insertion, deletion, and lookup. Git bisect uses binary search to find the commit that introduced a bug. Numerical methods use bisection to find roots of equations. Any time you can halve the problem space with a single test, you're applying the binary search principle — one of the most fundamental ideas in computer science.