ISRO2014-28

Question

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?

• A. 3.00              
• B. 3.46                  
• C. 2.81                
• D. 3.33

Comments

I am not getting the calculation of average number of comparisons...please explain me.

Answer 1

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.

Comments

@pooja, is the question asking for the average no. of comparisons for the searching of all the elements of the list one by one?

---

I don't understand the comparison 1,4,12,16 how u have calculated this please explain.

---

Edited..

---

thanx sir .

---

thank you for mam corcting  . i was completly wrong here

---

what r the comparisons in each level ?

---

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

---

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.

---

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

---

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.

---

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

Answer 2

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.

Comments

@shivani If you have any doubt you can ask anything ?

---

Simple and clear explanation

---

thanks bro     

---

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

Answer 3

b).

Average time complexity of binary search algorithm is log₂N.

here N=11, so ans = log₂ 11 = 3.46

Answer 4

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$