The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+7 votes
3.8k 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
asked in Algorithms by Active (3.3k points) | 3.8k views
0
I am not getting the calculation of average number of comparisons...please explain me.

3 Answers

+13 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.
answered by Boss (31.7k points)
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.
0
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

0
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.
0
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
+18 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.

answered by Boss (38.8k points)
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

answered by (23 points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,813 questions
47,492 answers
145,725 comments
62,251 users