Technology & Computing · Software & algorithms
Searching a million items
See why a sorted list of a million items takes about 20 checks to search, when sorting first is worth the effort, and how a hash table skips the search altogether.

What you will learn
- Explain why binary search can discard half of an ordered list.
- Identify the sorting condition that binary search needs.
- Estimate how repeated halving scales as a list grows.
- Tell an operation count apart from a measured running time.
Lesson 1 of 4 · 4 min
Why a sorted list is so much faster to search
Say someone hands you a million names printed in no particular order and asks you to find one. All you can do is read down the list.
That's linear search. You check the entries one after another until the name turns up or the list runs out. With luck it's near the top. If it's near the end, you read almost a million names. At one name a second, that takes more than 11 days.
Now put the same names in alphabetical order, like a phone book, and open it near the middle. Say you land on M and you're looking for Rivera. Every name before M is ruled out in one look.
Next you open the part that's left near its middle and do the same again. That's binary search. Each check throws away half of what remains, where linear search throws away one name.
Try it on the ordered numbers 3, 8, 12, 19, 25, 31 and 40, and say you're looking for 31. First compare it with the middle value, 19. Since 31 is larger, you can rule out 19 and the three values below it.
That leaves 25, 31 and 40. Check the middle of those, and you've found the target in two checks. Reading from the left would have taken six.
The shortcut depends entirely on the order. Shuffle those seven numbers and say 19 still sits in the middle. Now 31 could be on either side, so 19 tells you nothing. Throw away the left half and you might throw away the answer.
The order also has to match the question. A phone book is sorted by name, so it's no help for finding who owns a given number. For that search, the book might as well be shuffled.
Try to recallWhy is it unsafe to use binary search's discard-half rule on a shuffled list?
In a shuffled list, the middle value doesn't tell you which side holds the smaller or larger values, so the half you throw away could contain the target.
Lessons in this topic
Why a sorted list is so much faster to search
See how binary search rules out half of a sorted list with each check, and why the same move on a shuffled list can throw away the answer.
Why a million items take only twenty checks
Count the halvings that take a million candidates down to one, see what doubling the list costs, and learn why a count of steps isn't a time.
When sorting first is worth the effort
Work out when it's worth sorting a collection so that later searches go faster, and when a plain scan wins.
How a hash table finds things without searching
See how a hash function computes where an item belongs, and what that shortcut costs in collisions and memory.
Three quick stories from this topic
Lookup without searching
A well-sized hash table finds one item among a billion as fast as one among a thousand
It doesn't search. A hash function turns the item into a slot number, and the lookup goes straight to that slot. On average the cost stays the same at any size, as long as the table is big enough that few items share a slot.
A toy version uses first letters
File words by first letter, and apple goes to slot A and berry to slot B. To find berry, compute B again and go straight there.
Crowded slots are slow
Items that share a slot form a list that has to be checked one by one. A better hash function or a bigger table keeps those lists short, at the cost of memory.
Java's nine-year search bug
Java's built-in binary search hid a bug for about nine years before it broke a program
To find the middle, the code added two positions and halved the sum. On lists of about a billion items the sum grew too big for its number type and turned negative. Joshua Bloch, who wrote the code, published the fix in 2006.
One line was wrong
The faulty line averaged the low and high positions by adding them first. The fix subtracts first, so the numbers never grow larger than the list itself.
The textbook had it too
The same mistake sat in a well-known programming book for about two decades. Bloch's lesson was humility. It's hard to write even the smallest piece of code correctly.
Twenty checks for a million
A sorted list of a million names takes 20 checks to search, and a billion takes 30
Each check looks at the middle entry and rules out half of what's left. Twenty halvings take a million candidates down to one. Ten more halvings cover a list a thousand times longer.
The numbers behind the shortcut
Multiply twenty twos together and you get 1,048,576. Repeated halving undoes those doublings, which is why binary search's work grows so slowly as a sorted array gets larger.
There's a condition
The collection has to be sorted by the comparison you're using, and reaching its middle has to be practical. Twenty comparisons is a count of operations. It doesn't promise twenty milliseconds.
Sources
- Lecture 3 - CS50x 2025, Harvard University CS50
- Lecture 5 - CS50x 2025, Harvard University CS50
- Hash table, Wikimedia Foundation
- Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken, Google Research




