search
Log In
17 votes
2.5k views

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 ") ;
 }

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))$ ;
in Algorithms
edited by
2.5k views
3
Given progeam is errorneous bcz it is doing malfunction when we are serching for an element that not present in the array.

I.e. 10 20 30 40 50 60 70 80 90 100

Now search 65 it will go into infinite loop

And that problem occured due to improper index (i,j) updation.

and the correct updation is Option A which is followed by Binary Search.
1

3 Answers

25 votes
 
Best answer

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
0
manoj could u explain a bit more
9

@asu ... see .. suppose our array is - 1, 2, 3, 4,  5, 6

and we want to search x=7, then check what happens here-

In the beginning , i=0, and j=5.

k= (0 + 5)/2 = 2.

A[2] <7, so  i=k=2.


now while (A[2] != x&& i <j) - true

2nd time - i=2, j=5.

k= (2+5)/2= 3

A[3] < 7, so i=k=3


while(A[3] !=x && i<j) - true

3rd time - i=3, j=5.

k= (3+5)/2= 4.

A[4] < 7, so i= k=4.


while(A[4] !=x && i<j) - true

3rd time - i=4, j=5.

k= (4+5)/2= 4.

A[4] < 7, so i= k=4.


while(A[4] !=x && i<j) - true

3rd time - i=4, j=5.

k= (4+5)/2= 4.

A[4] < 7, so i= k=4.

.

.

.

 will go into infinite loop.

So to get rid of this infinite loop if we put- i = k+1. instead of i=k then it would not fall into infinite loop.

..

.and you can put j= k-1 and even j=k is also okay. 

 

.

 

0
@vijay...thank u for explaniation ....but to check each option it will take much time..any suggestion for these kind of question
1

Sorry @asu .. I am also working on it  ... but I think .. while reading BST .or any topic... if we consider every cases and especially edge case then we can solve most of the question related to any topic .. smiley

 

5

Is there any case in which::  if we update i=k+1 and keep j=k , then the given program will give erroneous answer??

As far as I understood. I think even i=k+1 and j=k will work fine.

but if we change

do{

}while(Y[k] !=x && i<=j)

then j=k-1 is necessary.

Correct me if I am wrong !!!

0
@VS

I think it will work fine for even j=k, no need to change to j=k-1
0
if array is {2,2,2,2,2,2,2,2,2,2} and we wat to search 3 now in this case option 1 will not work
1
if(Y[k]<x) then i=k+1 else j=k-1

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

Both will work fine.

Second one will work fine because loop terminates at $i \not \leq j$.

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

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

32 votes
5 answers
1
8k views
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 > 2$ $Y$ is $[2 \ 4 \ 6 \ 8 \ 10 \ 12 \ 14 \ 16 \ 18 \ 20]$ and $ 2 < x < 20$ and $x$ is even
asked Sep 11, 2014 in Algorithms Kathleen 8k views
24 votes
6 answers
2
2.6k views
Consider the following C functions: int f1 (int n) { if(n == 0 || n == 1) return n; else return (2 * f1(n-1) + 3 * f1(n-2)); } int f2(int n) { int i; int X[N], Y[N], Z[N]; X[0] = Y[0] = Z[0] = 0; X[1] = 1; Y[1] = 2; Z[1] = 3; for(i = 2; i <= n; i++){ ... X[i]; Z[i] = 3 * X[i]; } return X[n]; } $f1(8)$ and $f2(8)$ return the values $1661$ and $1640$ $59$ and $59$ $1640$ and $1640$ $1640$ and $1661$
asked Apr 23, 2016 in Algorithms jothee 2.6k views
17 votes
5 answers
3
1.5k views
Let $x_n$ denote the number of binary strings of length $n$ that contain no consecutive 0s. The value of $x_5$ is $5$ $7$ $8$ $16$
asked Apr 23, 2016 in Algorithms jothee 1.5k views
26 votes
2 answers
4
3.9k views
The subset-sum problem is defined as follows. Given a set of $n$ positive integers, $S = \{ a_1, a_2, a_3, \dots , a_n \}$, and positive integer $W$, is there a subset of $S$ whose elements sum to $W$? A dynamic program for solving this problem uses a $\text{2-dimensional}$ Boolean array, $X$ ... , implies that there is a subset whose elements sum to $W$? $X[1, W]$ $X[n, 0]$ $X[n, W]$ $X[n-1, n]$
asked Apr 23, 2016 in Algorithms jothee 3.9k views
...