The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

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

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

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.

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 6k
- Digital Logic 2.3k
- Programming & DS 4.3k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 16

40,965 questions

47,601 answers

146,686 comments

62,338 users