search
Log In
10 votes
6k views

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$
in Algorithms
edited by
6k views
0
I am not getting the calculation of average number of comparisons...please explain me.

4 Answers

19 votes
 
Best answer
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
0
@pooja, is the question asking for the average no. of comparisons for the searching of all the elements of the list one by one?
0
I don't understand the comparison 1,4,12,16 how u have calculated this please explain.
1
Edited..
0
thanx sir .
0
thank you for mam corcting  . i was completly wrong here
0
what r the comparisons in each level ?
0

Is there any importance of the line "all searches are successful in finding the item?"

1
yes, had the question been "comparisons". Then in case of a failed search we would have to do one more extra check to see if the tree is finished traversing.
0

arjun sir   both are similar question, one of the sol given by pooja and another one by happy mittle, which one is correct????

https://gateoverflow.in/16831/average-comparisons-binary-search-sorted-consecutive-starting

1
Both use the same approach, yet the one you've referred to in the URL has 10 elements and the one mentioned here has 11 elements. That's where the difference occurs.
1
I think the BST is to be balanced in order to get the answer as 3. For a normal BST with input 10,20,30, and so on.... If we create a BST with this input the BST will be skewed BST. In this case the average no of comparisons will be

For root 1 Comparision
For 2nd element 2 comparisons and so on...

Avg Comparisons in this case will be (11*12/2)/11=6
26 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
0
@shivani If you have any doubt you can ask anything ?
1

Simple and clear explanationyes

0

thanks bro      yes

0
this is clear explanation, but we cant use the average case of the binary search.???
0 votes

b).

Average time complexity of binary search algorithm is log2N.

here N=11, so ans = log2 11 = 3.46

0 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
1 answer
1
2.6k 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^2)$ $O(n!)$
asked Jul 1, 2016 in Algorithms jothee 2.6k views
4 votes
2 answers
2
2.6k views
Consider the following sorting algorithms. Quicksort Heapsort Mergesort Which of them perform in least time in the worst case? I and II only II and III only III only I, II and III
asked Jul 1, 2016 in Algorithms jothee 2.6k views
2 votes
2 answers
3
2.4k views
A computing architecture, which allows the user to use computers from multiple administrative domains to reach a common goal is called as Grid Computing Neutral Networks Parallel Processing Cluster Computing
asked Jul 1, 2016 in Distributed Computing jothee 2.4k views
6 votes
3 answers
4
2.7k views
Consider the following Deterministic Finite Automaton $M$. Let $S$ denote the set of eight bit strings whose second, third, sixth and seventh bits are 1. The number of strings in $S$ that are accepted by $M$ is 0 1 2 3
asked Jul 1, 2016 in Theory of Computation jothee 2.7k views
...