The question this module answers: where does the answer flip? Many questions have the shape "the first index where something becomes true": the first value ≥ x in a sorted list, the first checkpoint whose eval got worse, the smallest batch size that runs out of memory. If the yes/no question is monotone (all no, then all yes), you never need to look at every position. Ask in the middle, throw half away, repeat.
ML context. Binary search hides inside a lot of ML tooling:
- Thresholds and quantiles:
np.searchsortedandtorch.bucketizeplace values into sorted bin edges. - Regressions: "which of 64 checkpoints first broke the eval?" is answered with 6 evaluations, not 64.
- Capacity: the largest batch size or sequence length that fits in GPU memory (lesson 5.10).
- Sampling: drawing from a categorical distribution searches the cumulative probabilities.
1. The problem: scanning for the boundary
Task: in a sorted list, find the first index whose value is ≥ x (or len(a) if there is none).
The obvious way walks from the left until the condition holds.