Binary Search Question!

Question

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.

Comments

Similar to previous question :https://gateoverflow.in/132037/self-doubt-in-binary-search-algo

---

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

---

https://gateoverflow.in/16124/isro2014-28

this one too u can chk

Answer 1

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$

Comments

Thank you, Sir!