How can there be 10 steps in the binary search algorithm for the phone book search problem?

The following example was given in an online lecture I was watching.

A phone directory is 1000 pages long, and we have to find the name "Zurich Smith". The algorithm is as follows:

1. Split the phone directory into half. If the name is in the first half, get rid of the second half; and if the name is in the second half, get rid of the first half. Now we are left with 500 pages.

2. Repeat the above step another time, and we are left with 250 pages.

3. Repeat the above step another time, and we are left with 125 pages.

4. Repeat the above step another time, and we are left with 62 pages.

5. Repeat the above step another time, and we are left with 31 pages.

6. Repeat the above step another time, and we are left with 15 pages.

7. Repeat the above step another time, and we are left with 7 pages.

8. Repeat the above step another time, and we are left with 3 pages.

9. Repeat the above step another time, and we are left with 1 page.

**As you can see, these are 9 steps, but they, in the lecture, are saying that this algorithm involves 10 steps. Why? **

• Is this lecture viewable by the public at large and, if so, do you have a link? – derhabicht Sep 17 '15 at 16:54
• They might have made a small mistake. It's not very important. Don't spend too much time on it. – Yuval Filmus Sep 17 '15 at 18:22
• @derhabicht It is at 23:30 in this video lecture - the first lecture in CS50. But it is Harvard University, I really doubt there can be a mistake like that. – Solace Sep 17 '15 at 18:39
• @YuvalFilmus It is at 23:30 in this video lecture - the first lecture in CS50. But it is Harvard University, I really doubt there can be a mistake like that. – Solace Sep 17 '15 at 18:41
• @Solace You'd be surprised. Plus, as I said, it's a trifle. You're taking it too literally. The point is that $\log_2 1000 \approx 10$. – Yuval Filmus Sep 17 '15 at 18:54

but they, in the lecture, are saying that this algorithm involves 10 steps. Why?

He says:"10 - give or take" in the lecture, which means that 10 is an estimate with a small uncertainty in either direction. He accepted it as estimate from the audience, which replies to his question, either because he couldn't be bothered to calculate the correct result or because he didn't want to correct the audience that it's one less, because the correct number is completely irrelevant for what he tries to teach.

To find the right page using binary search would take at most $\lceil log_2 1000\rceil = 10$ steps, which I guess the lecture refers to. But that is not exactly what you do: note that there are a number of steps where you are left with an odd number $n$ of pages, and say that for the next step, you have $\lfloor n/2\rfloor$ pages; this means that you eliminate the page which is right in the middle (assuming that it doesn't contain the name, in which case you are done).

Doing it this way, nine steps are enough for $2^{10}-1 = 1023$ pages: After the $i$-th step, assuming you haven't found the name yet, the relevant half has $2^{10-i}-1$ pages left in it, which is $1$ for $i=9$.

• It is at 23:30 in this video lecture - the first lecture in CS50. They haven't talked about the logs so far.What you mention must be a sophisticated way of finding the number of steps, but he was explaining to students in an introductory lession the efficiency of an algorithm. – Solace Sep 17 '15 at 18:45
• He wouldn't necessarily throw logs at them - the gist is that in each step, the number of pages is cut in half, and 10 steps are enough to get from 1000 down to 1 this way. Turns out, you can do slightly better if in each step you get rid of a page altogether, hence 9 steps suffice. – Klaus Draeger Sep 17 '15 at 19:51
• At most 10, not at least 10. – Moby Disk Sep 18 '15 at 12:28

The algorithm you describe in your question gets you to the page that Zurich Smith's name is on, but it doesn't get to his name. So, steps 1-9 of your algorithm is simply getting rid of the pages that we know are irrelevant to what we want. The final step would be to simply search the last page to find the name. You could do another binary search, but at this point a linear search would be simple to implement and you wouldn't notice a performance hit in most cases.

In fact, that's a bit like how you would search a phonebook IRL. The first part is finding the page; by comparing index words, you know if you are ahead of or behind the name in the book. When you find the right page, you run your finger down the names on it until you find the one you want (or ones because this is usually the point when you find out how many "Zurich Smiths" live in your city but differentiating those is a completely different algorithm).

So, I would imagine step 10 is "Search the 1 page for 'Zurich Smith'." It might have been left out of the lecture because it might have been seen as a trivial step.

Step nine could have stated that you are left with 2 pages. Imagine having 3 pages, and dividing it by 2. One "half" contains 1, the other "half" contains 2. So no matter how you divide, at most you would do 10 steps. It is always possible to be quicker than 10 steps (eg. if it's exactly in the middle, you will find it in 1 step), and the steps above seem to be from and actual run through of the algorithm. If you run the algorithm for every single name, you will find that

• 1 whole page of names can be found in 1 step
• 2 whole pages of names can be found in 2 steps
• 4 whole pages of names can be found in 3 steps
• ...
• 489 whole pages of names can be found in 10 steps

And 489=1000-1-2-4-8-16-32-64-128-256

which is kind of cool if you think about it, there's a higher chance of finding the name in LESS than 10 steps. Now you just have to scan the page for his number..

There are 2 simplifications involved in the example.

1. It will take 10 steps if the book is 1024 pages, not 1000 pages.
2. The binary search will take at most 10 steps, not exactly 10 steps.

This is because $\lceil log_2 1024\rceil = 10$.