Core · Module 9
Binary search and search spaces
Halve the range every step, without the off-by-one bugs, and search answers as well as arrays.
Binary search answers questions about sorted data in O(log n): about 30 comparisons for a billion items. The idea fits in a sentence, but most implementations have bugs, so this module starts with a version built on a clear invariant. It then generalizes: finding boundaries instead of matches, searching over possible answers when there is no array at all, and handling rotated arrays and sorted grids.
- 1Binary search without off-by-one bugsPro — members onlyBinary search halves a sorted range at every step, so a billion items need about 30 comparisons. Writing it correctly comes down to one decision: what exactly the range means, and keeping that true.14 min
- 2Lower and upper boundsPro — members onlyInstead of asking whether a value is present, ask where the first element that is at least x sits. That one question finds first and last occurrences, counts duplicates and gives insertion points, with no special cases.13 min
- 3Searching an answer spacePro — members onlyWhen a yes-or-no check about a candidate answer flips exactly once, from no to yes, you can binary search over the answers themselves, even when no array exists.14 min
- 4Rotated and two-dimensional dataPro — members onlyBinary search still works when sorted data has been rotated, because one half of any range is always sorted. Sorted grids can be searched as one long array, or with a staircase walk from a corner.14 min