edited by
1,939 views
3 votes
3 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.

edited by

1 Answer

Best answer
3 votes
3 votes

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
Answer:

Related questions

0 votes
0 votes
2 answers
1
dhruba asked Jun 5, 2023
1,090 views
Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). ...
0 votes
0 votes
1 answer
2
Sabir Khan asked Aug 8, 2018
1,056 views
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is(A) (n)(B) (logn)(C) (log*n)(D) (1)
3 votes
3 votes
2 answers
3
rahul sharma 5 asked Mar 8, 2018
2,359 views
Why to prefer binary search over ternary search?Can someone give recreance relation for ternary search,so that i can compare both