Consider the C function given below. Assume that the array contains elements, sorted in ascending order.
int ProcessArray(int *listA, int x, int n)
{
int i, j, k;
i = 0; j = n-1;
do {
k = (i+j)/2;
if (x <= listA[k]) j = k-1;
if (listA[k] <= x) i = k+1;
}
while (i <= j);
if (listA[k] == x) return(k);
else return -1;
}
Which one of the following statements about the function is CORRECT?
View worked solution
Answer: B
The given function is an implementation of the binary search algorithm on a sorted array. Let's trace how the search space is updated in each iteration of the loop:
- Case 1:
Only the first conditionx <= listA[k]is satisfied. Thus,jis updated tok - 1, narrowing the search to the left half. - Case 2:
Only the second conditionlistA[k] <= xis satisfied. Thus,iis updated tok + 1, narrowing the search to the right half. - Case 3:
Both conditions are satisfied. Thus,jbecomesk - 1andibecomesk + 1. This makesi > j, causing the loop conditioni <= jto fail. The loop terminates, and the function correctly returns the indexkbecauselistA[k] == xholds true.
Since the search space [i, j] strictly shrinks in every iteration, the loop is guaranteed to terminate. Thus, the function is a valid implementation of binary search.
Free practice · Your answers on this page are not saved.