Blog

Binary Search in Depth: Lower Bound, Off-by-One and Binary Search on the Answer

The way to write binary search correctly is against an invariant, such as the half-open range [lo, hi); it makes at most 20 comparisons on 1 million elements, but a single boundary bug such as lo = mid sends it into an infinite loop. We write lower and upper bound, look at Array.BinarySearch's ~index return value, use binary search on the answer to find the minimum truck capacity and search a time range in a log, all with xUnit tests.