Binary search

Summary

Binary search finds a target value in a sorted array. It compares the target with the middle element of the remaining range and discards the half that cannot contain it. On an array of $n$ elements it uses at most $\floor{\log_2 n} + 1$ comparisons with array elements. It is the basic example of a logarithmic-time algorithm, and the same halving idea solves many search problems over monotone predicates.