binary search as divide and conquer

Looking up a word in a paper dictionary, you do not start at page one; you flip to the middle, see whether your word comes before or after, and throw away the half that cannot contain it. Repeat on the half that remains. Binary search is exactly this idea applied to a sorted array: by checking the middle element you eliminate half the remaining candidates with one comparison.

Precisely: to search for x in a sorted array A[lo..hi], compute the midpoint m. If A[m] equals x, you are done. If x < A[m], the answer can only be in the left half, so recurse on A[lo..m-1]; if x > A[m], recurse on A[m+1..hi]. The interval shrinks until it is empty (x not present) or you land on x. A correctness argument is a loop invariant: if x is anywhere in the array, it is always within the current [lo..hi] window. It holds at the start (the window is the whole array), each step discards only a half proven not to contain x so it still holds, and the loop ends when the window is one element (found) or empty (absent). This is a degenerate divide and conquer: it divides into two halves but conquers only ONE of them and needs no combine step.

Because each step halves the search space, binary search runs in O(log n) — for a million entries, about 20 comparisons. That logarithmic speed is why sorted structures are so valuable and underpins lower/upper-bound queries, square-root and root-finding by bisection, and any monotone predicate (binary search on the answer). The non-negotiable precondition: the array must already be sorted on the key you compare. Run binary search on unsorted data and it will confidently return wrong answers, because the half it discards may be exactly where the target lives.