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.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
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