Binary search is the best-known way to find a target in a sorted sequence. At each step we compare with the middle element and discard the half where the target cannot be. Time is O(log n): just 30 steps for a billion elements. For comparison, linear search is O(n).
![Searching for 23 in [2, 5, ..., 91]: three steps](img/lessons/algorithms/binary-search-trace.svg)
The algorithm and the invariant
We keep two bounds lo and hi that define the closed interval a[lo..hi]. Invariant: if x is in the list, it is in this interval. mid = (lo + hi) // 2 is the middle. If a[mid] == x, we found it. If a[mid] < x, x can only be on the right: lo = mid + 1. Otherwise on the left: hi = mid - 1. When the interval is empty (lo > hi), x is absent. Each step halves the interval, so there are at most floor(log2 n) + 1 steps.
