GATE CSE 2008 | Question: 84

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

On which of the following contents of $Y$ and $x$ does the program fail? 

• A. $Y$ is $[1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9 \ 10]$ and $x < 10 $  
• B. $Y$ is $[1 \ 3 \ 5 \ 7 \ 9 \ 11   \ 13 \ 15 \ 17 \ 19]$ and $x < 1 $ 
• C. $Y$ is $[2 \  2 \ 2 \ 2 \  2 \  2 \  2 \ 2 \ 2 \ 2]$ and $x > 2$ 
• D. $Y$ is $[2 \ 4 \ 6 \ 8 \ 10 \ 12 \ 14 \ 16 \ 18 \ 20]$ and $ 2 < x < 20$ and $x$ is even

Comments

What happens with OPTION B of the second question?

somebody help me analyse?

---

Assume x=0..ultimately u will come out of the loop when while cdn will fail i. E i<j

Bcz at the last point i n j will be equal to 0th position...

After cmng out of while loop.. Progrm is terminated aftr printing x is not in the array..

Hope it helps..

---

Option A 

take any value of x we are able to find by given algorithm because given algorithm fails on the last index element search because when you wanted to find last you are going from mid to right direction(increasing order of index) and when you have i=8 and j=9 you always get k=(8+9)/2  = 8 and this will repeat again and again and you never able to point the last index.

Option B

like option A explanation , you can point any index. So, ultimately when it is not present. It will print “x is not in array”. you can find the 1st element also. when i=0 and j=1 and gives you k=(0+1)/2 = 0 .

Option C

Same option A explanation you go from mid to right and at 8th index you stuck and can’t go forward.

option D

It’s also same explanation already explained you can find every element of array except last element. if  2<=X<20 then also it’s true. 

PS: one more thing to notice in option B when k=0 that means i=0 and j=1 is there and after that i=0 and j=0 then this do-while loop exit from this condition highlighted below.

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

Answer 1

Above code goes into infinite loop if element to be found is greater or equal to last element.

in option (C) we are searching for x>2 so it will go into infinite loop

Answer option (C)