331 views

### The average successful search time taken by binary search on a sorted array of 5 CONSECUTIVE integers starting with 1?

Kindly tell me is it correct or not?

NOTE: I have edited the question and changes are shown in highlighted text.

edited | 331 views
+1
It should be 2.

You will probe maximum 3 elements

First middle 3rd,now if not my element go left or right.

There we have two elements and we check middle(say first element).If it is the required element that we are done,else goto left or right

Now in that we have only one element. Compare with required element.

So total comparisons taken=1+2+3=6(1 first first element, 2 for second and so on).

Average =total comparisons/total elements 6/3=2
0

Man, total elements are 5. @rahul sharma 5

0
Yes. But in binary search you will probe only 3 elements. You cannot probe 5 elements. If you probe 5 elements then it is linear search
0
Is it 3/5 = 0.6 ?
+1
avg successful search time we need to know
So, search for a[(0+4)/2]=a[2]
then a[(2+4)/2]=a[3]
then a[4]
So, maximum search will be 3
among total 5 search
0
@srestha.

3 search will be worst case scenario

We have to give average case here.
0
@Rahul Sharma 5,In the worst case the element that is to be searched would possibly be at the last position. And in average case, the element would lie at the middle position. Isn't it?
0
how you all are getting 2.xxx , im doing this Log(n) - worst case and 1 in best case then avg will be (1+Log(n))/2 right ?
then (1+Log(5))/2 should be ans right ? which would be around less than 1... what am i missing ?
0

@rahul sharma 5 I have edited the question. Will you tell the answer now.

@srestha Miss, may you tell the answer now with the edited question.

0
Starting with 1 means first index is one or first element is 1?
+1
0

@ rahul sharma 5 Yes, similar question, but may you help me with mine with 5 elements?

0

+1 vote

There are 5 consecutive numbers starting with 1, so the numbers are

1,2,3,4,5 in the exact same order.

Suppose we use binary search to search for '1'.

then there will be three comparisons to find the number 1.

1. First we will check the middle element i.e, 3
2. Then we will check the left sub-array's middle element i.e, 2
3. And we continue in this manner till we find 1

So we will need 3 comparisons to find 1.

Likewise  we will need,

2 comparisons to find 2,

1 comparison to find 3,

2 comparisons to find 4,

3 comparisons to find 5.

Hence totally we need  $3+2+1+2+3 = 11$ comparisons.

The Average no. of Comparisons will be $11/5 = 2.2$

So the answer is $2.2$

selected by
0
Thank you, Sir!