LOGIC & PUZZLES / ALGORITHMS
Binary search:
eliminate half at a time.
One comparison can discard a large part of an ordered search space—if the order is trustworthy.
THE MAIN IDEA
Sorted information is what makes the shortcut possible.
Binary search finds a target in sorted data by examining the middle element and discarding the half that cannot contain the answer. If the middle value is smaller than the target and the list is ascending, every value before it is also too small. If the middle value is larger, every value after it is too large. Repeating this process reduces the candidate interval exponentially: a million entries can be narrowed to one in roughly twenty comparisons. That efficiency depends on a crucial precondition: the values must be sorted according to the exact comparison rule the search uses. Searching an unsorted list by repeatedly throwing away half is not clever; it simply loses valid candidates. Define the interval carefully as inclusive or half-open, and update its endpoints so the previous middle element is not reconsidered forever. Small lists often expose the classic off-by-one bug when the target is at the first or final position, or when the interval contains only two elements. Another ambiguity concerns duplicates: the ordinary algorithm may return any matching copy. If you need the first or last occurrence, the comparison and termination rules must be adapted to locate a boundary. A programming implementation also needs to compute the midpoint safely for its number type and match the data structure. Searching an array supports quick indexing, whereas a linked list cannot access its midpoint in constant time without traversal. Keeping a sorted copy costs memory and maintenance; binary search is not automatically the best choice if you make only one lookup in a tiny list. Tests should include empty input, one item, missing targets below and above the values, duplicates, and the smallest and largest entries. A linear scan provides a useful reference for checking results on randomly generated small arrays. The conceptual model is useful far beyond code. A “twenty questions” guessing game works when each yes-or-no question divides the remaining possibilities efficiently; a poorly chosen question that eliminates very little is like a lopsided search. The hidden value is not guessing better; it is preserving a range whose contents are known to remain sorted. Binary search is a small algorithm that rewards precise statements about invariants, boundaries, ordering, and what it means for a value to be found.
TRY THIS
Find a page number by halving.
Pick a page in a long book. Repeatedly open near the middle of the remaining range and decide which side contains the page. Count comparisons and test a page near each boundary. The book's page order is the necessary sorted-data condition.