Binary search finds a target in a sorted sequence by repeatedly discarding half of the remaining search interval.

For an ascending sequence, inspect the middle element:

• if it equals the target, the search is finished;
• if the target is smaller, continue in the left half;
• if the target is larger, continue in the right half.

After each comparison, the candidate interval is at most half as large. For $n$ elements, this gives

$$O(\log n)$$

comparisons in the worst case.

The essential invariant is that, if the target is present, it remains inside the current search interval.

Binary search depends on ordered random access. It does not provide the same benefit on an unsorted collection, and its midpoint and boundary updates must be defined carefully to guarantee termination.