Binary search

Binary search finds something in a sorted list by repeatedly cutting the search range in half. You look at the middle item: if your target is smaller, you throw away the right half; if larger, the left half. Like opening a dictionary in the middle and flipping toward the right letter, each step halves what’s left, so a million items take about 20 looks. The more general version finds a boundary: the first spot where some yes-or-no condition flips from false to true. That lets you binary search over possible answers, such as the smallest capacity that works, even when there’s no array at all. It’s simple to state but easy to get off by one.