somebody help me analyse?

Consider the following C program that attempts to locate an element $x$ in an array $Y[ \ ]$ using binary search. The program is erroneous.

f (int Y[10] , int x) { int u, j, k; i= 0; j = 9; do { k = (i+ j) / 2; if( Y[k] < x) i = k;else j = k; } while (Y[k] != x) && (i < j)) ; if(Y[k] == x) printf(" x is in the array ") ; else printf(" x is not in the array ") ; }

On which of the following contents of $Y$ and $x$ does the program fail?

- $Y$ is $[1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9 \ 10]$ and $x < 10 $
- $Y$ is $[1 \ 3 \ 5 \ 7 \ 9 \ 11 \ 13 \ 15 \ 17 \ 19]$ and $x < 1 $
- $Y$ is $[2 \ 2 \ 2 \ 2 \ 2 \ 2 \ 2 \ 2 \ 2 \ 2]$ and $x > 2$
- $Y$ is $[2 \ 4 \ 6 \ 8 \ 10 \ 12 \ 14 \ 16 \ 18 \ 20]$ and $ 2 < x < 20$ and $x$ is even

### 3 Comments

**Option A **

take any value of x we are able to find by given algorithm because given algorithm fails on the last index element search because when you wanted to find last you are going from mid to right direction(increasing order of index) and when you have i=8 and j=9 you always get k=(8+9)/2 = 8 and this will repeat again and again and you never able to point the last index.

**Option B**

like option A explanation , you can point any index. So, ultimately when it is not present. It will print “x is not in array”. you can find the 1st element also. when i=0 and j=1 and gives you k=(0+1)/2 = 0 .

**Option C**

Same option A explanation you go from mid to right and at 8th index you stuck and can’t go forward.

**option D**

It’s also same explanation already explained you can find every element of array except last element. if 2<=X<20 then also it’s true.

PS: one more thing to notice in option B when k=0 that means i=0 and j=1 is there and after that i=0 and j=0 then this do-while loop exit from this condition highlighted below.

- do {
- k = (i+ j) / 2;
- if( Y[k] < x) i = k;else j = k;
- } while (Y[k] != x) &&
(i < j)) ;

## 5 Answers

when it is **option C** the control will continue to iterate as $i=8$ and $j=9$;

again and again $i$ will be assigned $k$ which itself equals $8$ as $\frac{8+9}{2}$ being stored in an integer type variable, will evaluate to $8$.

For option A, with $x=9, k$ will take the following values:

- $4$
- $6$
- $7$
- $8 - y[8] = 9, x$ found

For option D, with $x=10, k$ will take the following values:

- $4, y[4] = 10, x$ found

### 7 Comments

https://gateoverflow.in/2770/gate1996-18 is this question same .what is the difference between these two?

do { k = (i+ j) / 2; if( Y[k] < x) i = k;else j = k; } while (Y[k] != x) && (i < j)) ;

Here i=k and j=k creates the problem.

just do i=k+1 and j=k-1

when we search the elements which is not in array and that element in the range of first and last element results infinite looping. that is unsuccessful search and range should be inbetween first and last.

another problem when searching last element and greater than of last element.

### 3 Comments

1.Array should be sorted.

2.All the elements in the array should be distinct.

for Ques.84 option c is correct