Consider the following C program that attempts to locate an element x in an…
2008
Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous.
f (int Y[10] , int x) {
int i, j, k;
i= 0; j = 9;
do {
k = (i + j) / 2;
if( Y[k] < x) i = k;else j = k;
} while (Y[k] != x) && (i < j)) ;
if(Y[k] == x) printf(" x is in the array ") ;
else printf(" x is not in the array ") ;
}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));
Attempted by 5 students.
Show answer & explanation
Correct answer: A
Key fix: update the search bounds so the middle index is excluded: if (Y[k] < x) i = k + 1; else j = k - 1;
Why: assigning i = k or j = k can leave the interval unchanged (for example when k equals i), causing an infinite loop. Using k+1 and k-1 ensures the interval size decreases each iteration.
Corrected line (replace the original comparison branch): if (Y[k] < x) i = k + 1; else j = k - 1;
Recommendation: also use a standard loop condition that keeps the interval valid, for example while (i <= j) and check for equality inside the loop. That version is clearer and avoids dependence on Y[k] in the loop condition.
Example corrected approach (conceptual):
Initialize i = 0, j = 9.
Loop while i <= j:
Compute k = (i + j) / 2; if Y[k] == x then found; else if Y[k] < x then i = k + 1; else j = k - 1.
This preserves correctness and guarantees termination because each iteration reduces the interval size.