Binary search

Overview

Presents binary search and the precondition that the data is sorted.

Binary search repeatedly halves a sorted range, comparing the target with the middle element. It finds an element, or proves its absence, in logarithmic time.

The common bug is an incorrect loop boundary; write the invariant down before coding.