Consider the C function given below. Assume that the array listA contains n (>…
2014
Consider the C function given below. Assume that the array listA contains n (> 0) 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 ProcessArray is CORRECT?
- A.
It will run into an infinite loop when x is not in listA.
- B.
It is an implementation of binary search.
- C.
It will always find the maximum element in listA.
- D.
It will return −1 even when x is present in listA.
Attempted by 101 students.
Show answer & explanation
Correct answer: B
Key idea: the function repeatedly inspects the midpoint and narrows the search interval, which is the binary search approach.
At each loop iteration k = (i + j) / 2 picks a midpoint in the current interval [i, j].
The comparisons x <= listA[k] and listA[k] <= x move the upper bound to k-1 or the lower bound to k+1 (or both when listA[k] == x), so the interval strictly shrinks.
The loop stops when i > j. The code then checks listA[k] == x: if true it returns the index k, otherwise it returns -1.
If x appears multiple times, the function will return one occurrence; it does not guarantee the first or last occurrence.
Time complexity is O(log n) for a sorted array of n elements.