GATE CSE 2008 | Question: 85

Question

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 

• A. Change line 6 to: if $(Y[k] < x) i = k + 1$; else $j = k-1$; 
• B. Change line 6 to: if $(Y[k] < x) i = k - 1$; else $ j = k +1$; 
• C. Change line 6 to: if $(Y[k] < x) i = k$; else $j = k$;
• D. Change line 7 to: } while $((Y[k] == x) \&\& (i < j))$ ;

Comments

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.

---

Similar question

https://gateoverflow.in/25140/tifr2012-b-11

---

Someone please edit the question. I got confused in option A and D, as there is opening bracket missing on line 7, after while loop. It should be :

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

in place of :

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

 

Answer 1

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.

Comments

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$.

---

@Ayush Upadhyaya

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

 

Second one will work fine because loop terminates at i$\nleqslant$j

 but according to me loop terminates at i=j.

Lets take an example,

index   :       0   1   2   3    4

elements:    5   6   7   8    9

Now, if i wanted to search x=9

then, k=(0+4)/2 = 2

then, k=(3+4)/2 = 3   (here i=3 and j=4)

 after , highlighted statement execute.

 

do {
        k = (i+ j) / 2;
        if( Y[k] < x) i = k+1;else j = k;
        } while (Y[k] != x) && (i < j)) ;

 

this will make i=4 and j=4.

and after that see do while loop condition it has to be i<j.

So, just exit.

---

@VS

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.

 if you do this i<=j your program will give errorneous result . see just above comment follow it just assume your x=10 and after when i=4 and j=4 then this time also loop will run one more time and 

k=(4+4)/2 = 4 and after that Y[k]<x means  9<10 obviously we do i=k+1 and i=5 now.

you just crossed the array index. look above index only from 0 to 4.

Answer 2

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.

Answer 3

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