Consider the following program that attempts to locate an element
2008
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 i, 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) printf ("x is in the array ") ;
9. else printf (" x is not in the array ") ;
10. }
On which of the following contents of Y and x does the program fail?
- A.
Y is [1 2 3 4 5 6 7 8 9 10] and x < 10
- B.
Y is [1 3 5 7 9 11 13 15 17 19] and x < 1
- C.
Y is [2 2 2 2 2 2 2 2 2 2] and x > 2
- D.
Y is [2 4 6 8 10 12 14 16 18 20] and 2 < x < 20 and x is even
Attempted by 6 students.
Show answer & explanation
Correct answer: C
Diagnosis: The code can enter an infinite loop because it updates the bounds with i = k or j = k. When the integer midpoint k equals the lower bound i (for example when i and j differ by 1), assigning i = k does not shrink the interval and k stays the same, so the loop never terminates for targets that are greater than all array elements or otherwise never found.
Concrete failing example:
Array: all entries = 2, target x = 3.
Start: i = 0, j = 9 -> k = (0+9)/2 = 4 -> Y[k] < x so i = k = 4.
Then k = (4+9)/2 = 6 -> i = 6; then k = 7 -> i = 7; then k = 8 -> i = 8; next k = (8+9)/2 = 8 again, so i stays 8 and the loop never makes progress.
Correct fix: Ensure the search interval strictly shrinks on each update. A standard correct binary-search loop is:
Initialize i = 0, j = n-1.
While i <= j do:
k = (i + j) / 2
If Y[k] == x, report found and exit.
Else if Y[k] < x, set i = k + 1 (not i = k).
Else set j = k - 1 (not j = k).
If the loop ends without finding x, report not found.
Why this fixes the problem: Using k+1 and k-1 guarantees the interval shrinks on every update, so k cannot remain equal to i (or j) indefinitely. This prevents the infinite-loop scenario described above and yields a correct binary search for sorted arrays.