edited by
952 views
0 votes
0 votes

The question is based on the following program fragment.

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

  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 
edited by

1 Answer

1 votes
1 votes
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.
Answer:

Related questions

1 votes
1 votes
2 answers
1
0 votes
0 votes
0 answers
2
admin asked Apr 1, 2020
555 views
The following program fragment printsint i = 5; do { putchar(i+100); printf(“%d”, i ;) } while(i);i5h4g3f2el14h3g2f1e0An error messageNone of the above
0 votes
0 votes
1 answer
3
admin asked Apr 1, 2020
914 views
An algorithm is made up pf two modules $M1$ and $M2.$ If order of $M1$ is $f(n)$ and $M2$ is $g(n)$ then the order of algorithm is$max(f(n),g(n))$$min(f(n),g(n))$$f(n) + ...