Average Number of comparisons in Binary search

What is the average number of comparisons in binary search on a sorted array of 10 consecutive integers starting from 1?

3Comments
shivanisrivarshini shivanisrivarshini 13 Jun 2016 05:40 pm

(1*1+2*2+4*3+3*4)/10 =(1+4+12+12)/10 =29/10 =2.9

 

Vivek Vikram Singh vivek14 13 Jun 2016 06:02 pm

Good approach given above. Another good reading on this matter can be found on this link http://www.techtud.com/resource-share/average-case-analysis

Jeevan Singh Nayal jsnayal 20 Jun 2016 05:33 pm

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

According to me, in 1 comparison i get 5 becoz 5 is in middle then in 3 comparisons i get 2 becoz 1 comparison for checking index 5 i.e 5 which is not 2, and 1 more comparison to move left or right of 5. I move left. So now middle is 2. So 3 comparisons for 2. In this way all the comparisons are found.

According to me, no of comparisons are

1- 5c

2-3c

3-5c

4-8c

5-1c

6-7c

7-5c

8-3c

9-5c

10-7c

avg=49/10=4.9

Please tell me where i am going wrong!!