GATE CS 2014 Set 3 Q.52 (CS Q.42): Searching and Sorting Algorithms

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?

It will run into an infinite loop when x is not in listA.

It is an implementation of binary search.

It will always find the maximum element in listA.

It will return -1 even when x is present in listA.

Official answer and solution

Official answer: B
From: Official GATE 2014 answer key

Solution

Analyze the loop invariant and termination conditions of the ProcessArray function.

Inspect ProcessArray(int *listA, int x, int n):
- The array listA is sorted in ascending order with $n > 0$ elements.
- Pointers $i = 0$ and $j = n - 1$ .
- Inside the do-while loop:
  - $k = (i + j) / 2$ chooses the midpoint.
  - If $x \le listA[k]$ , search interval shrinks on the right: $j = k - 1$ .
  - If $listA[k] \le x$ , search interval shrinks on the left: $i = k + 1$ .
When $x == listA[k]$ :
- Both conditions $x \le listA[k]$ and $listA[k] \le x$ are satisfied.
- Consequently, both updates execute: $j = k - 1$ and $i = k + 1$ .
- This immediately causes $i > j$ , so the do-while (i <= j) loop terminates.
- After the loop, the check if (listA[k] == x) is evaluated. Since $k$ still holds the index where $listA[k] == x$ , it successfully returns $k$ .
When $x < listA[k]$ :
- Only $j = k - 1$ updates, halving the search space to the left.
When $x > listA[k]$ :
- Only $i = k + 1$ updates, halving the search space to the right.
When $x$ is not present:
- The loop terminates with $i > j$ , and listA[k] != x, returning $-1$ .

Thus, this function is a correct implementation of binary search (option B).

Final answer

Common trap

Assuming that setting both i and j when x == listA[k] causes an error, whereas it cleanly terminates the search and returns k.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2014 Computer Science and Information Technology (CS) Session 3
Question: 52 of 65, printed as CS Q.42
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source