Binary search

Binary search needs two things: a sorted search space, and a safe way to rule out half of it. The most reliable form finds the first True. Write a yes/no test that answers False for a while and then True from some point on. Keep a range of candidates from lo up to (not including) hi. If the middle answers True, the first True is there or earlier, so set hi = mid. If False, it's later, so set lo = mid + 1.

pub fn first_true<F>(n: usize, mut predicate: F) -> usize
where
    F: FnMut(usize) -> bool,
{
    let (mut lo, mut hi) = (0, n);
    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if predicate(mid) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    lo
}

If nothing answers True, the result is n. The code never tests n itself. Everything below lo is known False, and everything from hi on is known True. Each step shrinks the range. The caller has to supply a test that really does go False, then True, and never back.

To find where a value goes in a sorted list, test a[i] >= target. To binary search on the answer, first turn "find the best" into a yes/no question. In Koko Eating Bananas, ask whether a given speed finishes in time. A faster speed never takes longer, so the answers go False, then True. Search for the smallest speed that works, after checking that your upper bound always works.

The cost is O(log R × C), where R is the size of the range you search and C is the cost of one test. Calling it O(log n) hides a full scan if each test looks at every element. Use 64-bit numbers when adding up hours, and round up the division without overflowing.

Finding a peak and searching a rotated sorted list use related ideas, but their values don't go False-then-True across the whole list. Learn those arguments separately. And sorted input doesn't always call for binary search.

Practice: LC 704 Binary Search, LC 35 Search Insert Position, LC 34 Find First and Last Position, LC 875 Koko Eating Bananas, LC 1011 Capacity To Ship Packages Within D Days, LC 33 Search in Rotated Sorted Array.

Check your understanding: What exactly is the yes/no question? Why does a True answer stay True for larger values? What does it return if every answer is False? Why can't the loop repeat the same range? See S9 for more on binary search boundaries and searching on the answer.