0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Presumably the answer is a positive integer, so you just need to figure out two positive integer values which bound the 'exact' answer, for which you just need your fingers. $\endgroup$ – user247608 Apr 27 '16 at 22:59
  • $\begingroup$ I can't get the exact answer without a calculator $\endgroup$ – J.Doe Apr 27 '16 at 23:00
  • 1
    $\begingroup$ What is log2 of 1024 and 2048? $\endgroup$ – user247608 Apr 27 '16 at 23:01
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ That was the key! I didn't think of rounding 62.5 up so the math got big! Thanks! $\endgroup$ – J.Doe Apr 27 '16 at 23:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.