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?
Best Answer
You can do this with simple arithmetic You have 2000 elements
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