0
Challenge · 31Sort & Search

Binary search on a sorted array

Patternsused in ~100% of apps

Twenty guesses is enough to find any name in a phone book of a million. Everyone understands the idea in five seconds and gets the code wrong on the first try, so this lesson is mostly about the three lines people get wrong.

Core idea. Look at the middle. That one comparison tells you which half the answer cannot be in, so you throw that half away and repeat. Each step halves the search space, which is why a million items take twenty steps instead of a million.
Playground, this isn't a screenshot
finding 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
2
5
8
12
16
23
38
56
72
91
16 < 23 → the answer is to the right, lo = 5
2
5
8
12
16
23
38
56
72
91
56 > 23 → the answer is to the left, hi = 6
2
5
8
12
16
23
38
56
72
91
found at index 5

Ten items, three comparisons. A million items would take twenty. The count grows by one every time the list doubles.

↑ play a little first, then dig in