edited by
13,365 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

3 votes
3 votes
The function is iterative implementation of Binary Search using Do while loop.
1 votes
1 votes
Suppose we have 6 elements in array indexed from 0 to 5 with same values in it.

we have to search for 4.

i=0 j=4 then k =2

now

i=3 j=4 k=3

now

i=4 j=4 k=4 (we got the required elements in k)

now

i=5 j=3  now while condition fails and loop terminates

now x==A(k)=4

so binary search succeded
0 votes
0 votes
(b) it is an implementation of binary search

It is finding an element X in an array

If search is found returns its position

else returning -1
Answer:

Related questions

50 votes
50 votes
9 answers
1
go_editor asked Sep 28, 2014
16,275 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$$...