edited by
13,363 views
58 votes
58 votes

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?

  1. It will run into an infinite loop when $x$ is not in $listA$.
  2. It is an implementation of binary search.
  3. It will always find the maximum element in $listA$.
  4. It will return −$1$ even when $x$ is present in $listA$.
edited by

10 Answers

Best answer
35 votes
35 votes
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$
edited by
55 votes
55 votes

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

17 votes
17 votes
B)....
6 votes
6 votes
above code is implementation of binary search
Answer:

Related questions

50 votes
50 votes
9 answers
1
go_editor asked Sep 28, 2014
16,273 views
Consider the following rooted tree with the vertex labeled $P$ as the root:The order in which the nodes are visited during an in-order traversal of the tree is$SQPTRWUV$$...