The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote

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 Veteran (20.3k points)
edited by | 135 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?


Please log in or register to answer this question.

Related questions

+1 vote
1 answer
+2 votes
1 answer
asked Nov 23, 2017 in Algorithms by saxena0612 Veteran (11.8k points) | 166 views
+1 vote
0 answers
asked Nov 16, 2017 in Algorithms by saxena0612 Veteran (11.8k points) | 113 views

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

34,266 questions
40,978 answers
39,885 users