GATE CSE 2014 Set 3 | Question: 42

Question

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?

• A. It will run into an infinite loop when $x$ is not in $listA$.
• B. It is an implementation of binary search.
• C. It will always find the maximum element in $listA$.
• D. It will return −$1$ even when $x$ is present in $listA$.

Comments

Why is ProcessArray called again,if it is a BINARY SEARCH?

---

If someone believes that option (A) is also correct, then following is the counter example:

Suppose
listA={10, 20, 30, 40, 50}

i=0;
j=4;
x = 60;

k = (0+4)/2 = 2

listA[2] <= 60; hence i=k+1 = 3

k = (3+4)/2 = 3

listA[3]<= 60; Hence i = k+1 = 4;

k = (4+4)/2 = 4

listA[4] <= 60, hence i=k+1 = 5

Now, i>j, so loop terminates and returns -1.

---

It seems like option D is also correct

---

@Nain

How you are getting that. Please provide an example.

Answer 1

When listA[k]=x;
then due to if(x<=listA[k]), j will be k-1
and due to if(listA[k]<=x), i will be k+1
thus, i>j because for every positive value of k, (k+1)>(k-1). So the loop will be terminated.
So it is a perfect working of Binary Search.

Answer 2

Consider : 

10

20

30

40

50

 

x=30
i 0 j 4 k ?
==iteration 1==
i 0 j 1 k 2
==iteration 2==
i 1 j 1 k 0
==iteration 3==
i 2 j 1 k 1
listA[k] = 20 != x
returns -1

but it can return the correct index sometimes

x = 20
i 0 j 4 k ?
==iteration 1==
i 0 j 1 k 2
==iteration 2==
i 1 j 1 k 0
==iteration 3==
i 1 j 0 k 1
listA[k] = 20 == x
returns 1

so the algorithm is partially correct