The GATE Grind

GATE 2016 CS – Question 44

Programming and Data Structures · Arrays · 2 marks · Multiple choice

The following function computes the maximum value contained in an integer array `p[]` of size $n$ ($n \geq 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

  1. `a != n`
  2. `b != 0`
  3. `b > (a + 1)`
  4. `b != a`

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) `b != a`

Explanation

Each step discards the smaller of `p[a]` and `p[b]`, moving `a` up or `b` down, so the maximum always stays between positions `a` and `b`. The loop must run until only one element remains, which is when `a == b`. At that point `p[a]` is the maximum, so the condition is `b != a`.