Binary Search

Binary search is a fast way to find something in a sorted list by repeatedly cutting the search space in half—like guessing a number between 1 and 100 by asking “higher or lower?” Imagine a dictionary: you don’t start at page 1 and flip forward one page at a time. You open roughly in the middle, see whether the word you want would come earlier or later alphabetically, then jump to the middle of that half, and so on. Each step discards half the remaining possibilities. In algorithm form, you keep two “bookends” around where the answer could still be: - low: the left boundary index (smallest possible position) - high: the right boundary index (largest possible position) - mid: the middle index between low and high - target: the value you’re searching for - A[mid]: the middle element you compare against At each step: 1) Look at mid. 2) If A[mid] == target, you’re done. 3) If A[mid] < target, the target can only be on the right half → move low to mid+1. 4) If A[mid] > target, the target can only be on the left half → move high to mid$-1$. Why it’s famously fast: after k steps, you’ve reduced the remaining candidates from n to about n/2^k. You stop when that’s ~1, which happens when 2^k ≈ n, i.e. k ≈ log2(n). That’s where the O(log n) time comes from: doubling the data only adds about one extra step.

The underlying idea—find something in an ordered set by repeatedly halving the possibilities—predates modern computers (it’s the same logic as efficient guessing games and using a phone book or dictionary). Binary search became important once early computing faced a new bottleneck: machines could compute quickly, but memory was limited and slow to scan. If you stored data in sorted form, a halving strategy dramatically reduced comparisons. The method was described in early computer-era writings (mid-1940s), and its analysis and clean presentation were later popularized in the computer science canon—especially through Donald Knuth’s work, which emphasized careful reasoning about correctness and running time. Interestingly, binary search is also notorious for being easy to get subtly wrong (off-by-one errors), which made it a classic teaching example for algorithmic rigor.

Pioneered by: No single definitive discoverer (the idea is a natural consequence of ordered search). One of the earliest published descriptions in the computing literature is often attributed to John Mauchly (1946). The algorithm was later formalized and widely popularized through computer science texts, notably by Donald Knuth.

• Looking up a word in a dictionary or a name in a printed phone book (conceptually the same halving strategy)
• Finding a record by ID in a sorted database index (and as a building block inside many indexing/data-structure operations)
• Searching timestamps or events in sorted logs to find the first/last occurrence around a time window
• “Insert position” tasks: finding where a new item should go in a sorted list to keep it sorted (used in scheduling, leaderboards, ranked lists)
• Computing boundaries like the first value >= x or last value <= x (common in analytics, rate tables, configuration thresholds)