GATEBOOK-DSA4_8

Question

Consider a sorted array A of n integer elements, A[0]...A[n − 1].

A search operation is to be performed on this array using .Binary search algorithm. If the element being searched is in fact the last element of the array, what is the difference between the index of element being searched and the index of the mid element computed in the third round of search algorithm? (Ignoring the ceil and floor functions for indices)

$(A)\frac{7n-7}{8}$

$(B)\frac{5n-6}{6}$

$(C)\frac{n-1}{8}$

$(D)\frac{3n-3}{4}$

My analysis

Before first iteration $i=0,j=n-1$ and element being searched has index=$n-1$

During First iteration

$mid=\frac{0+(n-1)}{2}= \frac{n-1}{2}$, since $a[mid] \lt search\,element$, so

After first iteration

$i=\frac{n-1}{2}+1,j=n-1$

During second iteration $mid=\frac{\frac{n-1}{2}+1+n-1}{2}=\frac{3n-1}{4}$

Since $a[mid] \lt x$

So after second iteration

$i=\frac{3n-1}{4}+1,j=n-1$

During third iteration

$mid=\frac{\frac{3n-1}{4}+1+n-1}{2}=\frac{7n-1}{8}$

So,difference between the index of element being searched and the index of the mid element computed in the third round of search algorithm

$(n-1)\,- \frac{7n-1}{8}=\frac{n-7}{8}$

This is my answer.But it matches none of the options. Where I went wrong?

Comments

if we take total 9 element and keeping track of mid element then option c is satisfied.

---

@BASANT KUMAR-But is should not be value specific right? How would I know otherwise, that taking this value will give me this correct answer.

---

i am just randomly pick a number but  by using  general approach i am also getting n-7/8.