edited by
6,901 views
24 votes
24 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 ") ;
 }

The correction needed in the program to make it work properly is 

  1. Change line 6 to: if $(Y[k] < x) i = k + 1$; else $j = k-1$; 
  2. Change line 6 to: if $(Y[k] < x) i = k - 1$; else $ j = k +1$; 
  3. Change line 6 to: if $(Y[k] < x) i = k$; else $j = k$;
  4. Change line 7 to: } while $((Y[k] == x) \&\& (i < j))$ ;
edited by

3 Answers

Best answer
29 votes
29 votes

Answer should be A.

if( Y[k] < x) then i = k + 1;

if given element that  we are searching is greater, then searching will be continued in the upper half of array

otherwise $\mathbf{j = k - 1}$;

in the lower half.

Take few case in consideration i.e.

  1. All elements are same
  2. Increasing order with no repetition
  3. Increasing order with  repetition.
edited by
5 votes
5 votes
Just try to search Last element : it will go into infinite loop because of interger division.

i=k+1 will solve the problem.

lets elemets are : 10 20 30 40 50 60 70 80 90 100

now try to search 25 or 35 or 45 or 55 on above array so it will run into infinite loop.

so we need both the conditions=i=k+1 and j=k-1

P.S: This program is errorenous because of unsuccessful search.
2 votes
2 votes

There are 2 changes to be made:

1. updation conditions : i=k+1 and j=k-1 //reason can be found in other ans

2.while loop condition : while (Y[k] != x) && (i < = j) //equal to added here , other ans missed this

let a[]={1,2,3,4,5,6,7,8,9,10};

Without 2nd condition f(a,10) will fail

 
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$