edited by
11,044 views
11 votes
11 votes

The average successful search time taken by binary search on a sorted array of $10$ items?

  1. $2.6$
  2. $2.7$
  3. $2.8$
  4. $2.9$

Answer is $2.9$

My doubt:- But when I am using $log_2n$ for $n = 10$ it is not equal to $2.9$, and $log_210 = 3.3219$ ?

edited by

2 Answers

Best answer
14 votes
14 votes
Here time means the average number of comparisions....
It is binary search.
Draw a binary search tree with 10 elements (Take any set of 10 numbers & draw a BST)
You will see number of nodes are ..
1 root .. then two nodes ...then 2 nodes from each ... at last 3 nodes in leaf..
1+ 2+ 4 + 3 = 10 you know.
So you may have to go through these heights to get the elements.
Average comparisions = ( 1*1 + 2*2 + 3*4 +  4*3  ) / 10    =    29/10  = 2.9
selected by
8 votes
8 votes

The 10 items i1, i2, ..., i10 may be arranged in a binary search trees as in Fig below. To get i5, the number of comparision needed is 1; for i2, it is 2; for i8 it is 2; for i1 it is 3, and so on. The average is (1+(2+2) +(3+3+3+3)+(4+4+4))/10, i.e., 2.9.

sorting tree

Answer:

Related questions

0 votes
0 votes
1 answer
1
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)
4 votes
4 votes
1 answer
2
Aghori asked Nov 5, 2017
1,162 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 require...
5 votes
5 votes
4 answers
3
Raushank2 asked Jun 28, 2017
2,629 views
I/p - Sorted array of n elementO/p- find any two elements a and b such that (a+b)>1000if lenear search is possible then go to Binary Search and Find time complexity ..?
0 votes
0 votes
2 answers
4
dhruba asked Jun 5, 2023
1,091 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). ...