Binary search is very easy to mess up. Here's my intuition - with it, my binary searches work first time, every time, with no off-by-ones.
This is loosely based off of We Need To Talk About Binary Search, which is a great explanation but is a bit finicky with its +1s, -1s and best_so_fars.
- Binary search is about finding when a predicate function flips. That is, below a certain unknown value it's always false/true, and above that it's always the other value.
- Visually, it's a step function but you don't know where the "step" is.
- Write your predicate. Actually write it out - define a function and everything. It makes the code for the binary search much nicer to read and reason about. We'll get into examples of predicates below.
- **The loop invariant for binary search