retagged by
29,509 views
5 votes
5 votes
retagged by

3 Answers

Best answer
27 votes
27 votes
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$$
edited by
14 votes
14 votes
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$.
1 votes
1 votes

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

 

 

 

 

 

Answer:

Related questions

0 votes
0 votes
2 answers
1
dhruba asked Jun 5, 2023
1,089 views
Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). ...
2 votes
2 votes
2 answers
3
Rohan Mundhey asked Nov 9, 2016
5,390 views
How many comparisons are needed for a binary search in a set of 64 elements?