BinarySearch
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. f (int Y [10] int x) {
 int u, j, k;
 i = 0; j = 9;
 do {
 k =(i + j) / 2;
 6. if (Y [k] < x)i = k;else j = k;
 7. } while ((Y [k]! = x) & & (i < j));
 if (Y [k] = = x) pr int f (" x is in the array ");
 else pr int f (" x is not in the array ");
 }
Y is [1 2 3 4 5 6 7 8 9 10] and x < 10
 
Y is [1 3 5 7 9 11 13 15 17 19] and x < 1
 
Y is [2 2 2 2 2 2 2 2 2 2] and x > 2
 
Y is [2 4 6 8 10 12 14 16 18 20] and 2 < x < 20 and x is even

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. f (int Y [10] int x) {
 int u, j, k;
 i = 0; j = 9;
 do {
 k =(i + j) / 2;
 6. if (Y [k] < x)i = k;else j = k;
 7. } while ((Y [k]! = x) & & (i < j));
 if (Y [k] = = x) pr int f (" x is in the array ");
 else pr int f (" x is not in the array ");
 }
Change line 6 to: if (Y[k] < x) i = k + 1; else j = k1;
 
Change line 6 to: if (Y[k] < x) i = k  1; else j = k+1;
 
Change line 6 to: if (Y[k] <= x) i = k; else j = k;
 
Change line 7 to: } while ((Y[k] == x) && (i < j));

Question 2 Explanation:
f(int Y[10], int x)
{
int i,j,k;
i=0;j=9;
do
{
k=(i+j)/2;
if(Y[k]
i=k+1;
else
j=k1;
} while (Y[k]!=x && i
if (Y[k]= =x)
printf(“x is in the array”);
else
printf(“x is not in the array”);
}
{
int i,j,k;
i=0;j=9;
do
{
k=(i+j)/2;
if(Y[k]
else
j=k1;
} while (Y[k]!=x && i
printf(“x is in the array”);
else
printf(“x is not in the array”);
}
There are 2 questions to complete.