3.2k views

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 | 3.2k views
0
Why is ProcessArray called again,if it is a BINARY SEARCH?
+4
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.

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$.
edited by
B)....
+31

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

0
Thanks for the hint, :) I was wondering how it was coming out of the loop.
+1
nice explanation would you mind expanding the answer a bit, it is extremely useful (pun intended)

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

above code is implementation of binary search
0
Can you explain how ???
0
Could you pease explain, how option A is wrong. For array A={1, 2, 3, 4, 5} and K=10, then im getting  infinite iterations... Please help
0
Assume array contains 1,2,3,4. Will the above code give us correct answer? Please guide.
0
you are right ..even i have same doubt.and that is correct also(i feel).can any one explain why A option wrong
0

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

The function is iterative implementation of Binary Search using Do while loop.
+1 vote
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
+1 vote
The function is iterative implementation of Binary Search.

k keeps track of current middle element.

i and j keep track of left and right corners
of current subarray
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.

1
2