Comparisons in a Binary Search

Question

How many comparisons are needed for a binary search in a set of 64 elements?

Answer 1

in quetion not mentaioned that Array is sorted or not :

I assume it is sorted . it will take log₂n for n elements.

So for 64 it takes 6 comparision atmost for any element. Comparision on elements 32, 16, 8, 4, 2,1 

Comments

yes, we do not have more information here. At least choice could have helped.

---

A). 6

B). 14

C). 12

D). None of the above  :) :) :)

---

@kapil If we consider that one compare operation gives us all the information (wether the element being searched is to be searched on the left part or right or already found), then logN does represent the number of compare operations in the worst case for an array of $2^N$ elements.

1, 2, 3, 4, 5, 6, 7, 8
suppose we are searching for 0. first comparison with 4. now we know we have to search on left portion. so compare with 2, then with 1. total 3 comparisons. $2^3$ = $8$

Answer 2

we know that recurrance relation for binary search with n elements is:

f(n) = f(n/2) + 2

now, f(64) = f(32) + 2

        f(64) = (f(16) + 2) +2

        f(64) = (f(8) + 4) +2

        f(64) = (f(4) + 6) +2

        f(64) = (f(2) + 8) +2

        f(64) = (f(1) + 10) +2

now, f(1) equals to 2 since two comparisons are required for one number

         this gives f(64) = 14