The following function computes the maximum value contained in an integer array of size .
int max (int *p,int n) {
int a = 0, b=n-1;
while (__________) {
if (p[a]<= p[b]) {a = a+1;}
else {b = b-1;}
}
return p[a];
}
The missing loop condition is:
View worked solution
Answer: D
The given function uses a two-pointer approach to find the maximum element in an array of size . Let's analyze how the algorithm works:
- We initialize two pointers:
a = 0(pointing to the start of the array) andb = n - 1(pointing to the end of the array). - In each iteration of the loop, we compare the elements at these two pointers:
- If
p[a] <= p[b], the element atais smaller than or equal to the element atb. Thus,p[a]cannot be the unique maximum element of the array. We can safely discard it by moving the left pointer forward:a = a + 1. - Otherwise, if
p[a] > p[b], the element atbis strictly smaller than the element ata. Thus,p[b]cannot be the maximum element. We discard it by moving the right pointer backward:b = b - 1. - In each step, exactly one element is eliminated from being the candidate for the maximum.
To find the maximum among elements, we must perform exactly eliminations. The process should stop when only one element remains in our candidate space, which occurs when the two pointers meet, i.e., when a == b.
Therefore, the loop must continue as long as there is more than one element left, which means a != b (or equivalently, b != a).
Thus, the missing loop condition is b != a.
Free practice · Your answers on this page are not saved.