The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+2 votes

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

My Answer is - 2.2

Kindly tell me is it correct or not?

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

asked in Algorithms by Loyal (9.6k points)
edited by | 410 views
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

Man, total elements are 5. @rahul sharma 5

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
Is it 3/5 = 0.6 ?
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

3 search will be worst case scenario

We have to give average case here.
@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?
how you all are getting , 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 ?

@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.

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

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


1 Answer

+3 votes
Best answer

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$

answered by (183 points)
selected by
Thank you, Sir!

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
48,435 questions
52,746 answers
68,219 users