The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
2.5k 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$.
asked in DS by Veteran (101k points)
edited by | 2.5k views
0
Why is ProcessArray called again,if it is a BINARY SEARCH?
+2
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.

8 Answers

+12 votes
Best answer
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$.
answered by Loyal (9.4k points)
edited by
+15 votes
B)....
answered by (137 points)
+29

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.
0
nice explanation would you mind expanding the answer a bit, it is extremely useful (pun intended)
+9 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

answered by Active (1.8k points)
+3 votes
above code is implementation of binary search
answered by Boss (31.7k points)
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?

+2 votes
The function is iterative implementation of Binary Search using Do while loop.
answered by Active (4.7k points)
+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
answered by Active (1.9k points)
+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
answered by Loyal (8.4k points)
0 votes
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.
answered by (11 points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,848 questions
46,815 answers
141,153 comments
59,066 users