Lesson 3 of 4
Searching and halving.
Two ways to find a name in a list: check them one by one, or open the middle and throw half away. Why binary search needs a sorted list, and how the base-two logarithm counts the halvings it needs.
Step 1 of 5 · Linear search
Step 1 of 5
Linear search
The simplest way to find a name in a list is to go through it from the start, name after name, until you find it. That is a linear search, and it works on any list, sorted or not. How much work is it? When algorithms are compared, the usual question is about the worst case: the most it might have to do.
Step 2 of 5
Binary search
Nobody looks up a word in a dictionary that way. You open it in the middle, see whether the word there comes before or after the one you want, and throw the other half away. Then the middle of what is left, again. That is binary search: every check halves the list.
Step 3 of 5
How many halvings
How many halvings shrink a list of 1024 names to one? The same question backwards: how many doublings take one name to 1024? On the board, Growth per step is fixed at 2: each step doubles the stack, and Steps sets how many times.
The number of doublings of 2 that reach is the base-two logarithm, . Binary search in sorted names needs about checks.
Step 4 of 5
A list twice as long
A linear search through a list twice as long does twice the work. What about binary search? On the board, the stack after ten steps already reaches 1024.
Step 5 of 5
A million
Look inside is open at Log scale: each doubling raises the stack by the same height, so exponential growth is a straight line. The logarithm turns multiplying into adding, which is why even huge lists need few halvings. A board of twelve steps only reaches 4096; work out the million yourself.
Loading the interactive version…
Loading the interactive version…
Each step sets up the Scene for you, and a control marked “fixed” stays put for that step.
Practice · Calculate
In an unsorted list of 1000 names you look for one name, checking them one by one from the start: a linear search. In the worst case, how many names do you have to check?
Practice · Calculate
In an unsorted list of 1000 names you look for one name, checking them one by one from the start: a linear search. In the worst case, how many names do you have to check?
Practice · Choose
Binary search opens the list in the middle, checks whether the name there comes before or after the one you want, and throws away the half the name cannot be in. What must be true of the list?
Practice · Choose
Binary search opens the list in the middle, checks whether the name there comes before or after the one you want, and throws away the half the name cannot be in. What must be true of the list?
Practice · Reach the target
On the board each step doubles the stack; binary search goes the same way backwards, and halves. Change Steps until the last column reaches 1024, and press Check. That is the number of halvings that shrink 1024 names to one.
Practice · Reach the target
On the board each step doubles the stack; binary search goes the same way backwards, and halves. Change Steps until the last column reaches 1024, and press Check. That is the number of halvings that shrink 1024 names to one.
Practice · Predict, then look
In 1024 sorted names binary search needs ten checks. How many will it need in 2048 names, twice as many?
Practice · Predict, then look
In 1024 sorted names binary search needs ten checks. How many will it need in 2048 names, twice as many?
Practice · Calculate
A sorted phone book of a million names. At most how many checks does binary search need? (Hint: , nearly a thousand.)
Practice · Calculate
A sorted phone book of a million names. At most how many checks does binary search need? (Hint: , nearly a thousand.)
Lesson complete. Every practice question here is done.