## Binary-Search

 Question 1
Consider the following C program that attempts to locate an element x in an array Y[ ] using binary search. The program is erroneous.
1. 1. f (int Y  int x) {
2. int u, j, k;
3. i = 0; j = 9;
4. do {
5. k =(i + j) / 2;
6. 6. if (Y [k] < x)i = k;else  j = k;
7. 7. } while ((Y [k]! = x) & &  (i <  j));
8. if (Y [k] = = x) pr int f (" x is in the array ");
9. else pr int f (" x is not in the array ");
10. }
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
Algorithms        Binary-Search       Gate-2008
Question 1 Explanation:
This 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[ ]. In such case, program goes in an infinite loop because i is assigned value as k in all iterations, and i never becomes same/ equal to or greater than j. So while condition never becomes false.
 Question 2
Consider the following C program that attempts to locate an element x in an array Y[ ] using binary search. The program is erroneous.
1. 1. f (int Y  int x) {
2. int u, j, k;
3. i = 0; j = 9;
4. do {
5. k =(i + j) / 2;
6. 6. if (Y [k] < x)i = k;else  j = k;
7. 7. } while ((Y [k]! = x) & &  (i <  j));
8. if (Y [k] = = x) pr int f (" x is in the array ");
9. else pr int f (" x is not in the array ");
10. }
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));
Algorithms        Binary-Search       Gate-2008
Question 2 Explanation:
f(int Y, int x)
{
int i,j,k;
i=0;j=9;
do
{
k=(i+j)/2;
if(Y[k] i=k+1;
else
j=k-1;
} while (Y[k]!=x && i if (Y[k]= =x)
printf(“x is in the array”);
else
printf(“x is not in the array”);
}
There are 2 questions to complete.