Binary Search
Loading
Loading
Binary Search
Stop thinking about values and start thinking about a predicate.
By the end of this chapter
Searching for a value is the least interesting thing binary search does. The general form is: there is a predicate over a range which is false up to some point and true from then on, and you want the boundary.
predicate over indices 0..7F F F F T T T Tthe predicate flips exactly oncemid = 3 → Fthe flip is to the right; discard 0..3mid = 5 → Tkeep 5 as a candidate; discard 6..7lo = hi = 4boundary foundboundary at index 4def first_true(lo, hi, predicate): """Smallest x in [lo, hi] with predicate(x) true; hi + 1 if none.""" while lo < hi: mid = lo + (hi - lo) // 2 # cannot overflow if predicate(mid): hi = mid # mid might be the answer: keep it else: lo = mid + 1 # mid definitely is not: discard it return loConcept
When hi == lo + 1, floor division makes mid == lo. If the predicate holds, hi becomes lo and the loop ends. If it does not, lo becomes lo + 1 == hi and the loop ends. Either branch shrinks the interval, which is exactly what an inclusive hi with `hi = mid` fails to guarantee.
Quick quiz
Sign in to keep a note here. It is free, and nobody else can see it.
Sign inWhat this chapter was for:
Before moving on: take the quiz above.