The GATE Grind

GATE 2014 CS (CS3) – Question 52

Algorithms · Searching, Sorting and Hashing · 2 marks · Multiple choice

listA contains n > 0 elements sorted in ascending order. Which statement about ProcessArray is correct?

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;
}

  1. It loops forever if x is absent.
  2. It implements binary search.
  3. It always finds the maximum element.
  4. It returns −1 even when x is present.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) It implements binary search.

Explanation

Each iteration checks the midpoint and eliminates the impossible half. At equality both bounds move past the midpoint, ending the loop, and the final equality check returns its index. Otherwise it returns−1after the interval empties. Hence **binary search,B**. The nonempty-array premise makes the initial midpoint valid.