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. 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 = k-1;
| |
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=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”);
}
{
int i,j,k;
i=0;j=9;
do
{
k=(i+j)/2;
if(Y[k]
else
j=k-1;
} 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.