in Algorithms edited by
12,264 views
38 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 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 ") ;
 }

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
in Algorithms edited by
12.3k views

3 Comments

What happens with OPTION B of the second question?

somebody help me analyse?
0
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..
5
edited by

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)) ;
1

5 Answers

37 votes
 
Best answer

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

7 Comments

please explain the difference between

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

and
if (Y[k] < x) i = k - 1; else j = k +1; 
0
But the same index 8 problem will also arise for option (a), when you are searching for say x=9.. Can somebody explain dat plz?
0
As I solved for option D, with $$x=10$$, the code seems to go in infinite loop. So option D is also incorrect. Please correct me if I am wrong.
0
for x = 10 in option D, it will find k = (0 + 9)/2 = 4 and Y[4] = 10. the while loop will exit, giving you the answer. There is no infinite loop in that.
0

https://gateoverflow.in/2770/gate1996-18  is this question same .what is the difference between these two?

1
@arjun sir

but same problelm arises with option b if x=0 which is not present then we will no get any result.then b and c both should be wrong.why we are only seeing c option?
0

In option B, i and j both become equal to 0 at the last iteration and hence we break out of the while loop.

https://ideone.com/KrxmCc

1
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
84. The answer is C.

Binary search fails if all the elements are same.

85. The answer is A.

3 Comments

How binary search fails when all elements are same?
7
The errorfull nature of this program is not related with "what type of elements are stored in array" .the error is regarding "what element we want to search..if the element we want to search is more than or equal to last element of array,it will cause problem as program will never terminate ..
8
If all elements are equal then searching element should be greater than the array element..in just that case it should just exactly greater..
1
3 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

4 Comments

The second one is not a requirement. It happens here just because code is wrong. See

https://gateoverflow.in/43508/gate2008-85

7
Explanation: The above program doesn’t work for the cases where element to be searched is the last element of Y[] or greater than the last element (or maximum element) in Y[]. For such cases, program goes in an infinite loop because i is assigned value as k in all iterations, and i never becomes equal to or greater than j. So while condition never becomes false. So ans is option :C
3
@Arjun sir  why second condition is not necessary for binary search (distinct element) please explain in detail.
0
becouse if all elements same

ex. 2,2,2,2,2

and if you want to search 2 with binary search you will get in the 1 phase itself

and if you search other than the element present in the array

obiviously  you will get false simple
0
0 votes

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) 

by
Answer:

Related questions