The following function computes the maximum value contained in an integer…
2016
The following function computes the maximum value contained in an integer array p[ ] of size n (n >= 1).
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:
- A.
a != n
- B.
b != 0
- C.
b > (a + 1)
- D.
b != a
Attempted by 77 students.
Show answer & explanation
Correct answer: D
Answer: The correct loop condition is b != a.
Key idea: Maintain two indices at the ends of the array and eliminate one element per iteration by comparing p[a] and p[b].
Procedure: compare p[a] and p[b]; if p[a] <= p[b], increment a to discard p[a]; otherwise decrement b to discard p[b].
Termination: run while a and b are different (b != a). When they meet at index i, p[i] is the maximum.
Why other conditions fail: comparing indices to array bounds (like a != n or b != 0) can cause out-of-bounds access or incorrect termination; stopping when b > a+1 can end with two elements left and returning the left one may be wrong.
Example: For p = [1, 3, 2], start a=0, b=2. Since 1 <= 2, a becomes 1. Now compare p[1]=3 and p[2]=2; since 3 > 2, decrement b to 1. Now a==b==1 and return p[1]=3.
Complexity: O(n) time and O(1) extra space.
A video solution is available for this question — log in and enroll to watch it.