Binary search

What you will be able to do

After this lesson you can

• explain how binary search halves the list at each step,
• write binary search with a low, a high and a middle,
• follow it by hand for a target that is there and one that is not, and
• say what happens if the list is not in order.

The guessing game idea

You played the number guessing game: "Too high", "Too low". A good player does not guess 1, 2, 3. A good player guesses the middle each time, and halves the possibilities. Binary search does exactly that. It needs one thing: the list must be in order.

Think of a dictionary of 1000 pages. To find a word, you do not read from page 1. You open it in the middle, see whether your word comes before or after, and then you open the middle of that half. In ten openings you reach the page.

Predict first. The program looks for 23 in a sorted list of 10 numbers. How many steps will it need? Then run it.

It needed 3 steps. Follow the output with the picture.

1. low is 0 and high is 9. The middle position is (0 + 9) // 2 = 4, and it holds 16. We want 23. Since 16 is smaller than 23, everything up to position 4 can be thrown away: low = middle + 1.
2. Now low is 5 and high is 9. The middle is 7, and it holds 56. That is bigger than 23, so everything from position 7 can be thrown away: high = middle - 1.
3. Now low is 5 and high is 6. The middle is 5, and it holds 23. Found.

Notice the three ideas of the loop.

• The loop continues while low <= high, which means that there is still something left to look at.
• Each step moves either low up or high down. It always goes past the middle (middle + 1 or middle - 1), because the middle has just been checked. If you wrote low = middle, the loop could go on for ever.
• When low becomes bigger than high, nothing is left, and the target is not there: the answer is -1.

The second call, for 10, shows a failed search: the range closes in until there is nothing left, in 4 steps.

How fast is it?

Each step halves the list. So the number of steps is about the number of times that you can halve the list before one item is left:

Look at the last row. A million items, and only 20 checks. If you double the length of the list, binary search needs only one more check. That is the power of the method. The price: the list must be sorted first.

The numbers along the top are some of the items: the list must be in order, or throwing away half could throw away the target.

What if the list is not in order?

After sorted(messy), the same function finds it. So the rule is: binary search works only on a sorted list, and it fails quietly if the list is not. Always sort first, or be sure that the data is already in order.

When to use which

• A short list, or a list not in order, and only one search: linear search.
• A long sorted list, or many searches on the same list: binary search. (Sorting costs something, but you pay it once, and then every search is fast.)

Python has a module for this, bisect, which does binary search for you. It is good to know that it exists. It is also good to know how it works, which is why you write it yourself here.

Common mistakes

• A list that is not sorted. A quiet wrong answer.
• while low < high instead of <=. The last item is never checked.
• low = middle instead of middle + 1. An endless loop.
• Forgetting the whole numbers: (low + high) / 2 is a decimal number, and cannot be a position. Use //.
• Forgetting that positions start at 0.

Practice

Start with two quick questions. Each New numbers gives you a fresh one, so you can practise as long as you like.

Then the labs and the problems:

1. Warm-up. Open the problem How fast is binary search? and the problem Which search?
2. Build. Open the lab Search a sorted list. You write binary search, and the checker tries it on many lists, with targets that are there and not there.
3. Stretch. Open the lab A race: linear against binary and watch the number of checks.

Remember these

• Binary search needs a sorted list.
• It checks the middle and throws away half in each step.
• For 1 000 000 items it needs at most about 20 checks.
• On a list that is not in order, it gives wrong answers with no message.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. About how many checks does binary search need for 1000 items?

2. What does the loop condition low <= high mean?

3. Why must the list be in order?