edited by
21,123 views
47 votes
47 votes

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 i, 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

5 Answers

Best answer
46 votes
46 votes

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
edited by
13 votes
13 votes
 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.

edited by
4 votes
4 votes
84. The answer is C.

Binary search fails if all the elements are same.

85. The answer is A.
4 votes
4 votes
For binary search there are two necessary conditions:

1.Array should be sorted.

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

for Ques.84 option c is correct
Answer:

Related questions

24 votes
24 votes
6 answers
3
go_editor asked Apr 23, 2016
5,189 views
Let $x_n$ denote the number of binary strings of length $n$ that contain no consecutive $0$s.The value of $x_5$ is $5$$7$$8$$16$