Binary search
The conceptHow a million names can be searched in 20 checks
Binary search finds an item in a sorted list by checking the middle and discarding the half that can't hold it. To find 42 in 3, 8, 15, 23, 42, 56, 71, 90, check the middle (23); 42 is bigger, so the left half is out.
Two markers, lo and hi, bound where the answer can be. Each round checks mid = (lo + hi) / 2: a match stops; a bigger target moves lo to mid + 1, a smaller one moves hi to mid − 1. If lo passes hi, it isn't there.
Each check halves what's left, so the number of checks grows with log₂ n: O(log n) in Big-O terms. Going from a thousand items to a million only takes you from about 10 checks to about 20.
What it’s forGives the most checks binary search can need on a sorted list.
worst-case checks = ⌊log₂ n⌋ + 1
- n
- how many items are in the sorted list
- log₂ n
- how many times you can halve n before reaching 1
- ⌊ ⌋
- round down to a whole number
What it givesAn upper limit on the comparisons, which grows by just one each time the list doubles.
- n = 8: log₂ 8 = 3, so 3 + 1 = 4 checks at most
- n = 1,000,000: log₂ ≈ 19.93, rounded down 19, so 20 checks