retagged by
812 views
0 votes
0 votes
Find the average number of comparisons in a binary search on a sorted array of 10 consecutive integers starting from 1.

1) 2.6

2)2.7

3)2.8

4)2.9
retagged by

1 Answer

Best answer
1 votes
1 votes
option (D) is correct

average number of comparison(or searches) for successful search =(I(E)+n)/n where I(E) is the  path length of all  internal nodes(after considering external nodes in tree)and n is number of nodes

here given sorted elements of array so 1 element at level 1(root) then 2 elements at level 2 and 4 elements at level 3 and 3 elements at level 4

so number of comparison=(1*0+2*1+4*2+3*3+10)/10 =>2.9comparisons
selected by
Answer:

Related questions

0 votes
0 votes
2 answers
1
dhruba asked Jun 5, 2023
1,090 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). ...
0 votes
0 votes
1 answer
2
Sabir Khan asked Aug 8, 2018
1,056 views
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is(A) (n)(B) (logn)(C) (log*n)(D) (1)
1 votes
1 votes
4 answers
3
Abhishek Kumar 38 asked Dec 15, 2018
2,055 views
There are two sorted list each of length n. An element to be searched in the both the lists. The lists are mutually exclusive. The maximum number of comparisons required ...
2 votes
2 votes
4 answers
4
aditi19 asked Aug 20, 2018
2,568 views
for binary search in an array of n elements the average number of searches is $\left \lfloor \log_{2}n \right \rfloor$ or $\left \lceil \log_{2}n \right \rceil$ ?