Consider the following program that attempts to locate an element x in a…
1996
Consider the following program that attempts to locate an element x in a sorted array a[1..N] using binary search. Assume N > 1. The program is erroneous. Under what condition does the program fail?
i = 1;
j = N;
do {
k = floor((i + j) / 2);
if (a[k] < x)
i = k + 1;
else
j = k;
} while (a[k] != x && i < j);
if (a[k] == x)
print("x is in the array");
else
print("x is not in the array");
- A.
x is the last element of the array a[]
- B.
x is greater than all elements of the array a[]
- C.
Both of the above
- D.
x is less than the last element of the array a[]
Attempted by 20 students.
Show answer & explanation
Correct answer: A
The program uses a 1-indexed search interval with i = 1 and j = N. In each iteration it computes k = floor((i + j) / 2). If a[k] < x, it sets i = k + 1; otherwise it sets j = k.
Suppose x is the last element, i.e. x = a[N]. Since k is always less than N until the interval becomes very small, every checked a[k] is less than x. Hence the program repeatedly moves i to k + 1. Eventually i becomes N while j is also N, so the loop condition i < j becomes false.
The problem is that k still holds the previous middle position, typically N − 1. The final test checks a[k] == x instead of checking a[i] or a[N]. Therefore the program incorrectly prints that x is not in the array even though x is present as the last element.
If x is greater than all array elements, then x is not present, and printing that x is not in the array is correct. Therefore the program fails only when x is the last element of a[].