Calculating the amount of times a binary search could run (worse case) without a calculator/calculating base 2 logs without a calculator.

Question

Ok so I had a question on a test that I had to do without a calculator. And I can not figure out how in the world I am supposed to do it without a calculator.

The question asked to find how many times a binary search would calculate a midpoint (amount of iterations) given that the list was sorted and had 2000 elements.

I figured out (by reading) that the calculation should be log (2, elements + 1) the problem is calculating that without a calculator. Also I don't know whether to round, floor, or ceil that value.

How could you easily calculate log (2, n) without a calculator? Is this even the right formula?

Answer 1

You can do this with simple arithmetic You have 2000 elements

1. The largest list you'll get after splitting is then 1000 elements
2. Split again and get 500
3. Split again and get 250
4. Split again and get 125
5. Split again and get 63 (worst case)
6. Split again and get 32
7. Split again and get 16
8. Split again and get 8
9. Then 4
10. Then 2
11. Then you compare once more
12. And maybe check you have the answer in the list

So 12 comparisons in the worst case by my reckoning. In this calculation I include the midpoint in the refined list but you may get 10 or 11 if you don't. You may also not have an existence check at the end