edited by
12,766 views
14 votes
14 votes

Suppose there are $11$ items in sorted order in an array. How many searches are required on the average, if binary search is employed and all searches are successful in finding the item?

  1. $3.00$             
  2. $3.46$                  
  3. $2.81$                
  4. $3.33$
edited by

4 Answers

Best answer
21 votes
21 votes
if binary search tree is constructed, for root element one comparison for level 1, two comparisons and so on. There are 1, 2, 4 and 4 elements at levels 1, 2, 3, 4 respectively. So, avg. no of comparisons = (1*1+ 2*2+4*3+4*4)/11 = 3 as for level we need comparisons to reach there.

Ans is a.
selected by
30 votes
30 votes

Let us consider an array of 11 element which are sorted.

10 20 30 40 50 60 70 80 90 100 110

Now apply binary search in the given array .For convenience  we are using Binary search tree.

For first element (which is root) array will be

(10 20 30 40 50 ) 60 (70 80 90 100 110)

Now binary search continue either in lower or in upper halve for searching .

For lower halve (10 20) 30 (40 50).

For upper halve (70 80) 90 (100 110) and continued in same way.

So to search middle element (i.e 60 ) it will take 1 comparison .For 30 or 90 it will take 2 comparison .For 20 ,3 comparison and so on.

So avg No of comparison=$\large \frac{1+(2+2)+(3+3+3+3)+(4+4+4+4)}{11}=3$

So option A is correct.

reshown by
3 votes
3 votes

Binary search takes $O(nlogn)$ time. You can't just substitute 11 in place of n because $O$ actually represents some constant.

Let the array be {1,2,3,4,5,6,7,8,9,10,11}

Searching 6 would take 1 comparison.

Searching 3 or 9 would take 2 comparisons.

Searching 1 or 4 or 10 or 7 would take 3 comparisons.

Searching 2 or 5 or 8 or 11 would take 4 comparisons.

Average = $\frac{1*1+2*2+4*3+4*4}{11} = \frac{33}{11}=3$

 

Option A



 

Alternate method:

You can construct a BST of 11 nodes. No matter how you create it you'll end up with:-

  • 1 node in Level 0
  • 2 nodes in Level 1
  • 4 nodes in Level 2
  • 4 nodes in Level 3

For this question, let's consider the numbering of levels from 1. So:-

  • 1 node in Level 1
  • 2 nodes in Level 2
  • 4 nodes in Level 3
  • 4 nodes in Level 4

Average = $\frac{1*1+2*2+4*3+4*4}{11} = \frac{33}{11}=3$



 

PS: In case of unsuccessful search, we'd have added 1 comparison, so that we'd know the tree is over and search is unsuccessful.

It'd look like:-

  • 1 node in Level 1
  • 2 nodes in Level 2
  • 4 nodes in Level 3
  • 4 nodes in Level 4
  • +1 futile comparison.

Average = $\frac{(1*1+2*2+4*3+4*4)+1}{11} = \frac{34}{11}=3.09$

Answer:

Related questions

5 votes
5 votes
1 answer
1
go_editor asked Jul 1, 2016
4,870 views
What is the time complexity for the following C module? Assume that $n>0$.int module(int n) { if (n == 1) return 1; else return (n + module(n-1)); }$O(n)$$O(\log n)$$O(n^...
5 votes
5 votes
2 answers
2
go_editor asked Jul 1, 2016
6,468 views
Consider the following sorting algorithms.QuicksortHeapsortMergesortWhich of them perform in least time in the worst case?I and II onlyII and III onlyIII onlyI, II and II...
3 votes
3 votes
3 answers
3
go_editor asked Jul 1, 2016
3,247 views
Consider a 13 element hash table for which f(key)=key mod 13 is used with integer keys. Assuming linear probing is used for collision resolution, at which location would ...
3 votes
3 votes
1 answer
4
go_editor asked Jul 1, 2016
3,656 views
A computing architecture, which allows the user to use computers from multiple administrative domains to reach a common goal is called asGrid ComputingNeutral NetworksPar...