10 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?

- $3.00$
- $3.46$
- $2.81$
- $3.33$

19 votes

Best answer

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?

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

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.

0 votes

b).

Average time complexity of binary search algorithm is log_{2}N.

here N=11, so ans = log_{2 }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**

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$