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.

4 short lessons · about 17 minutes · 4 sources · updated November 2026

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

Before you readYou open a sorted phone book of a million names near the middle and land on M. You are looking for Rivera. How much of the book can you rule out in that one look?

Correct.Not quite. The answer is About half the book.

You can rule out about half the book in one look. This lesson shows why order lets a search throw away so much at once.

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.

Check yourselfYou're using binary search to find 8 in the ordered list 3, 8, 12, 19, 25, 31, 40, and you check 19 first. Which candidates are left?

Correct.Not quite. The answer is 3, 8 and 12.

Since 8 is smaller than 19, it can only sit to the left. Every value on the right is larger than 19, so none of them can be 8, and you drop them all at once. The sorting is what makes that safe.

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

  1. 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.

    Essentials · 4 min

  2. 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.

    Essentials · 4 min

  3. 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.

    Deeper · 4 min

  4. 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.

    Deeper · 5 min

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

This topic is part of What happens behind the screen, a guided path through related topics.

  • Why a computer can't write down one tenth

    Trace 0.1 into binary and back, and see why adding it three times doesn't give 0.3, why rounding first doesn't help, and what to do instead.

    4 lessons · 20 min

  • What an algorithm is

    An algorithm is a list of steps exact enough for a machine to follow. See how to write one, how to show it always finishes with the right answer, and why the word now covers looser things.

    4 lessons · 18 min

  • How programming works

    Most programs are built from a handful of ideas. See how variables, decisions, loops and functions fit together, and learn to read a short program line by line. No experience needed.

    4 lessons · 16 min

  • How a database keeps records consistent

    See how transactions, built-in rules and isolation levels keep records right when a server crashes, two buyers want one seat or two updates collide.

    4 lessons · 17 min

  • A web page's journey to your screen

    Follow a web address from name lookup to request and response, see what an error code tells you, and watch the browser turn the files into a page.

    4 lessons · 17 min

  • How processors execute instructions

    Follow a tiny calculation through the instructions, memory addresses and circuits that make a computer work.

    4 lessons · 22 min

All technology & computing topics · Take the quiz