Question

Average number of comparisons in a binary search on a sorted array of 10 consecutive int. starting from 1?

Comments

we have to assume the search is always successful here..

---

the link which u hv shared,showing 2 answers so m confused which 1 is correct?

---

Check the selected answer on the link :)

Answer 1

Its 2.9 on average; the question asked average number of comparisons on binary search; so as per algo first the middle, then since it is sorted while computing for the middle and equating to it at the same time it is determined which way to go further left or right;

1 2 3 4 5 6 7 8 9 10
For 5: 1
For 2,8 : on second comaprison, i.e., 2
And similarly
For 1,3,6,9: 3
And for 4,7,10: 4

compute it: $$\frac{1 \times 1 + 2 \times 2 + 4 \times 3 + 3 \times 4}{10} = 2.9$$

Answer 2

Array is [1,2,3,4,5,6,7,8,9,10].

Average number of comparisons depend on how likely each element is to be searched. Suppose each element is equally likely to be searched i.e. every element has 1/10 prob of being searched.

Now searching 5 takes only 1 comparison (it will be found in first trial only).

Then searching 2 or 8 takes 3 comparisons (1 for equality with 5, which was failed, then 1 for less than or greater than, then 1 for equality with 2 or 8).

Then searching 1 or 3 or 6 or 9 takes 5 comparisons (again 1 for less than or greater than, and 1 for equality)

Finally, searching 4 or 7 or 10 takes 7 comparisons.

So average number of comparisons = $\frac{1+2*3+4*5+3*7}{10} = 4.8$.

Comments

Answer is 2.9 or answer is 4.8 plz clarify

---

Its ambiguous. In GATE they will say which one they meant. Or else choice will help.

---

This is the correct answer.

Answer 3

given that 10 consecutive integers starting from 1 so the numbers are 1 2 3 4 5 6 7 8 9 10

for binary search we first compare with the mid value( low=0,high=9 (0+9)/2=4) )

if mid value is the required value then we require only one comparison(for 5:One comparison)

for 1 and 6 we require 2 comparisons (one comparison is for 5 another is for 1 or 6)

for 2 and 7 we require 3 comparisons (two from above comparison another is for 2 or 7)

for 3 and 8 we require 4 comparisons(three from above comparison another is for 3 or 8)

for 4 and 9 we require 5 comparisons(three from above comparison another is for 4 or 9)

therfore average is =(1*1+2*2+3*2+4*2+5*2)/10=2.9