TwiddleLab / Code / Algorithms in Motion

Linear vs Binary Search, Revisited

Lesson 2 of 11 · 7 min · Free, no account needed

What you will learn

• Linear search checks items one by one: up to n checks.
• Binary search checks the middle and drops half. It needs about log₂ n checks: 20 for a million.
• Doubling the data adds just one check to binary search.
• Binary search only works on sorted data.

Start the lesson

How the lesson goes

1. Find one username among a million. Is there a shortcut?

   The names are in alphabetical order. You look at the middle name and drop the half it can't be in, again and again. Bet how many names you'll look at.

2. The runner checks one by one. The jumper halves.

   Same shelf, same speed: one check per tick each. Run the race.

3. Be the jumper.

   63 books, names hidden, alphabetical order. Find the name in 6 checks or fewer.

4. Two ways to search.

   Linear search checks items one by one. On n items it can take n checks.

   Binary search checks the middle and drops the half that can't hold the answer. It needs about log₂ n checks: how many times n halves down to 1. A million: 20.

   Doubling the data adds just one check. That slow growth is called logarithmic time. The price: the data must be sorted.

5. Grow the shelf. When does the jumper need 30 checks?

   Each stop doubles the number of names.

6. Build your own binary search.

   It prints where the name is, or -1 if it isn't there. Three tests.

7. The search says kai isn't here. It is.

   Run the search, then tap the book that breaks it.

8. 1 048 576 sorted names. How many times can you halve that until 1 name is left?

   1 048 576 is 2 multiplied by itself some number of times. In math that number is log₂ 1 048 576.

   Each halving divides by 2. Twenty divisions by 2 take 2²⁰ = 1 048 576 to 1.

9. Find 63. Tap the books in the order binary search checks them.

   low = 0, high = 14, mid = (low + high) // 2.

10. Now search everyone on Earth.

    Slide from your class to the whole planet, sorted by name.

Previous lesson: Counting Steps · Next lesson: Selection Sort · Part of the course: Algorithms in Motion

Lessons are interactive and need JavaScript. Turn it on to play them.