Imagine searching for a word in a dictionary by starting at page one and checking every page in order. That would take an average of 500 page-turns for a 1,000-page dictionary. Now imagine opening to the middle, checking whether your word comes before or after, then repeating with the relevant half. That's binary search—and it finds any word in at most 10 steps, regardless of where it appears.
How Binary Search Works
Binary search requires a sorted list. Start with the entire list as your search space. Check the middle element. If it equals your target, you're done. If your target is smaller, discard the upper half. If larger, discard the lower half. Repeat with the remaining half until you find the target or exhaust the search space. Each comparison eliminates exactly half the remaining possibilities. Starting with n elements, after k comparisons you have n/2^k elements left. You finish when n/2^k = 1, requiring k = log₂(n) comparisons.
The Logarithm Is the Magic
The key insight is that binary search runs in O(log n) time, compared to O(n) for linear search. For small lists, the difference is modest. For large ones, it's transformative. Searching 1 billion elements: linear search requires up to 1,000,000,000 comparisons; binary search requires only about 30. That's because log₂(10⁹) ≈ 30. The logarithm grows so slowly that doubling the data size adds only one more comparison. This is why sorted data structures are so valuable—they enable logarithmic instead of linear search.
Real-World Applications
Binary search appears far beyond dictionary lookups. Databases use B-tree indexes that enable logarithmic search across millions of records. The Unix command grep uses binary search on sorted files. Git's bisect command uses binary search to find which commit introduced a bug—you mark commits as good or bad, and Git narrows down the culprit logarithmically through the commit history. Even physical applications use binary search: to calibrate where a thermostat triggers, you test temperatures above and below alternately, halving the range each time.
Variants and Extensions
Binary search has elegant variants. Lower bound search finds the first position where a target could be inserted while maintaining sorted order. Upper bound finds the last such position. Together they find all occurrences of a repeated element in O(log n) time. Ternary search extends the concept to finding minima or maxima of unimodal functions by dividing into thirds rather than halves. Exponential search first finds a range containing the target by doubling the range each time, then applies binary search—useful when the list is very large and the target is likely near the beginning.
When Binary Search Fails
Binary search requires two conditions: sorted data and random access (the ability to jump directly to any element). Linked lists fail the second condition—you can't jump to the middle without traversing from the start, making each 'jump' cost O(n) rather than O(1). Unsorted data fails the first condition entirely. In practice, the cost of sorting data for a single search may outweigh the benefit; binary search shines when you search repeatedly in the same sorted structure. Hash tables offer O(1) average lookup at the cost of losing ordering information.
Conclusion
Binary search is a perfect example of how the right algorithm transforms impossibility into ease. The shift from linear to logarithmic time complexity isn't just an improvement—it's the difference between a search engine that responds in milliseconds and one that takes hours on a trillion-document index. The core idea—eliminate half the possibilities with each query—appears throughout computer science, mathematics, and everyday problem-solving. Whenever you're searching through sorted structure and can determine which half contains your answer, you're doing binary search.