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

Problem Detail: 

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? **

Asked By : Solace

Answered By : Lars Friedrich

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47277