Binary Search - Average Number of Comparisons.

Question

Let you are given an array of nine elements in increasing order. If you want to implement binary search on the given array of element then the number of comparisons per successful search on an average will be:

---

Average is 2.78,

should I answer this question with or without rounding off 2.78, as number of comparisons is an integral value?

 

Comments

https://gateoverflow.in/16831/gateoverflow.in#viewbutton

Answer 1

It is to be answered without rounding off, i.e, 2.78 or whatever you calculated being the correct answer.

Answer 2

Let's take an example :-

$1,2,3,4,5,6,7,8,9$

It take $1$ comparison to search for $5$.

It takes $2$ comparisons to search for $2 \ and \ 7$.

It takes $3$ comparisons to search for $2,4,6 \ and \ 8$.

And it takes $4$ comparisons for $1,9$.

Thus average =$\frac{1+4*3+2*2+4*2}{9}=\frac{25}{9}=2.7777 = 2.78$

Comments

Searching for '2' takes 3 comparisons.

"It takes 2 comparisons to search for 2 and 7"

"It takes 3 comparisons to search for 2,4,6 and 8"

Why is no of comparisons required for 2 different for 2 cases?