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

That is the time complexity approximation, right ? It does not gives the number of comparisons

---

Kapil in worst case we need to one side from half of array na. so logn max comparision in worst case ?

M i missing somthing?

---

Its a formula type of a question,

I dont remember the formula, but somewhere i read that in the worst case, it uses 2 * Log₂(n + 1) maximum comparisons and its asymptotic upper bound is O(Log n).

---

this is taken from this site https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/

---

@Pavan, O(Log N) is the asymptotical number of comparisons needed.
But it is different from the actual number of worst case comparisons. I guess WC comparisons are 

2 * Log₂(n + 1) = 14 

---

from where did you got this formula...can you explain it ?

---

I tried it for a few cases by hand and I could only get maximum comparisons ceil(log(N)). How do you get 2*logN +1 ?

---

Formula given by kapil is correct. Cehck this http://stackoverflow.com/questions/10571170/how-many-comparisons-will-binary-search-make-in-the-worst-case-using-this-algori

---

formula is 2*Log(N-1)

= 2*ceil[log(63)]

= 2*6

Ans :12

---

formula given is 2*Log(N-1) in link not 2*Log(N +1)

---

i think it depends on the binary search implementation...

---

@Anirudh, See the 2nd answer in the link !! He has given exact upper bound

---

I will check it b/c in low answer says exact 2*Log(N-1)

BDW thankyou for pointing.

---

Isn't that stackoverflow link saying for that given implementation? Why do we increase the formula? :O

---

@Arjun Sir please check the discussions under the second answer here https://gateoverflow.in/16831/average-number-comparisons-binary-search-consecutive-starting According to the number of comparisons will be logN. So I think it depends on what we count as a comparison or if all the information is available in a single compare operation.

---

@Arjun Sir, But O(Log N) is the asymptotic number of comparisons. Are we going to use this ? I guess No.

---

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