The Gateway to Computer Science Excellence

+9 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

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

+24 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$

52,215 questions

60,027 answers

201,249 comments

94,712 users