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

This is an implementation of the Binary search algorithm.

Note that the loop will be terminated when we have found $x$. In that case both the if conditions will be true making condition inside the while as false i.e., $i>j$.

Correct Answer: $B$

Comments

Option B is correct because if element not present in the array the loop will not run infinite time.
e.g {10, 20, 30, 40, 50} and search 60 on this array.

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

after this loop will terminate. B part is correct

Answer 2

The trick is using <= in two if conditions.

if (x <= listA[k]) j = k-1;         
if (listA[k] <= x) i = k+1; 

So, at any time if A[k]=x then , both the if conditions will be executed, hence j=k-1 and i=k+1 will be set  => which will make sure that i>j( since (k+1)>(k-1)) and execution will come out of do-while loop.Answer B

Comments

OMG, did not spot it.

Somebody select this as best answer

---

yes

---

OMG wow❤️

how have u got this in mind

Answer 3

B)....

Comments

when x == A[k], both "if" conditions will be true and this where it gets out of loop, nice question :)

---

Thanks for the hint, :) I was wondering how it was coming out of the loop.

---

nice explanation would you mind expanding the answer a bit, it is extremely useful (pun intended)

Answer 4

above code is implementation of binary search

Comments

you are right ..even i have same doubt.and that is correct also(i feel).can any one explain why A option wrong

---

@Yashaswini :- Can you give any example where A is true?

---

AmitPatil

Maybe you're tracing it out wrong.

k = 0+4 / 2 = 2; i = 3

Then, k = 4+3 / 2 = 3; i = 4

Then k = 4+4 / 2 = 4; i = 5

Then break out of the while loop.

Then reutrn -1.