Direction: 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) {
2. int u, j, k;
3. i = 0; j = 9;
4. do {
5. k = (i + j)/ 2
6. if (Y[k] < x) i = k; else j = k;
7. } while ((Y[k]! = X) & &(i < j));
8. if (Y[k]) = = x) print f (“x is in the array”);
9. else print f (“x is not in the array”);
10. }
-
The correction needed in the program to make it work properly is
-
- 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))
- change line 6 to; if (Y [k] < x) i = k + 1; else j = k – 1;
Correct Option: A
The correction in the program is needed as in the above solution we can see that the program cannot work properly.
Now, when y[k] < x
Increase 1 to k + 1
Otherwise, decrease j to k –1
This will ensure that in the while condition, element at k position will be checked for equality.
