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. }
-
On which of the following contents of Y and x does the program fail?
-
- 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
- Y is [1 2 3 4 5 6 7 8 9 10] and x < 10
Correct Option: C
We are given that
i = 0; j = 9;
k = (i + j)/2
I iteration
Let consider x = 4
Now, k = (0 + 9)/2 = 4
Therefore, y[4] < x is true
→ i = 4 and j = 9
II iteration
As i = 4
Now, k = (4 + 9) / 2 = 6
Therefore, y[6] < x is true.
→ i = 6 and j = 9
III iteration
As i = 6
Now, k = (6 + 9) / 2 = 7
Therefore, y[7] < x is true
→ i = 7 and j = 9
IV iteration
As i = 7
Now, k = (7 + 9)/2 = 8
Therefore, y[8] < x is true
→ i = 8 and j = 9
V iteration
As i = 8
Now, k = (8 + 9) / 2 = 8
Therefore, y[8] < x is true
→ i = 8 and j = 9
As we have proved that 4[8]! = x & i < j, the program will remain forever in loop.
