688 views

The question is based on the following program fragment.

f(intY,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?

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

Answill be c

option c will be correct

first iteration

i = 0 ,j = 9

k = (0 + 9)/2 = 4

Elements with duplicate values of “2” the condition if(Y[k] <x) becomes true

second iteration

i = 0 , j = k =4

k = (0 + 4)/2 = 2

Elements with duplicate values of “2” the condition if(Y[k] <x) becomes true

third iteration

i = 0, j = 2

k = (0 + 2)/2 = 1

Elements with duplicate values of “2” the condition if(Y[k] <x) becomes true

Fourth iteration:
I=0, j=k=1
K= (0+1)/2=0

The while condition is Y[k] != x && i < j is true
● The above program doesn’t work for the cases where element to be searched is the last element of Y[ ] or greater than the last element (or maximum element) in Y[ ].
● For such cases, program goes in an infinite loop because i is assigned value as k in all iterations, and i never becomes equal to or greater than j.
● So while condition never becomes false.