GATE CSE 1996 | Question: 18

Question

Consider the following program that attempts to locate an element $x$ in an array $a[ ]$ using binary search. Assume $N > 1$. The program is erroneous. Under what conditions does the program fail?

var i,j,k: integer; x: integer;
    a: array; [1..N] of integer;
begin	i:= 1; j:= n;
repeat	
    k:(i+j) div 2;
    if a[k] < x then i:= k
    else j:= k
until (a[k] = x) or (i >= j);
    
if (a[k] = x) then
    writeln ('x is in the array')
else
    writeln ('x is not in the array')
end;

Comments

isn't this will also effect the loop (i >= j); i should be greater than j. ??

---

I am not getting the until part here.

---

what is the difference between these two ?

https://gateoverflow.in/394/gate2008-84

https://gateoverflow.in/2770/gate1996-18

---

exactly same Question repeated in the year 2008 gate cse paper. @once_2019

Answer 1

The code is wrong here

k=(i+j) / 2;
if (a[k] < x) then i = k;
else j = k;

The (correct) code should be:

k=(i+j) / 2;
if (a[k] < x) then i = k + 1;
else j = k - 1;

We can try an example with the given code in question

Let the array be $\qquad a[1,2,3,4,5,6,7,8,9,10]$
Index numbers$\qquad \quad1,2,3,4,5,6,7,8,9,10$
Let $x=10$; now run the code;

Initially $i = 1, j=10$;

first time  $k =(i+j) /2 = 11/2 =5.5 = 5$ (because of integer type) $=i$

second time $= k =(i+j) /2 =15/2 =7.5 =7 =i$

third time $=  k =(i+j) /2 = 17/2 = 8.5 = 8 =i$

fourth time $=  k =(i+j) /2 = 18/2 = 9 = i$

fifth time  $=  k =(i+j) /2 = 19/2 = 9.5 =9 = i$

sixth time $=  k =(i+j) /2 = 19/2 = 9.5 =9 = i$

seventh time $=  k =(i+j) /2 = 19/2 = 9.5 =9 = i$

---

Going to infinite loop (run time error)

For terminating the loop, it should be $i = k + 1$  instead of $i =k$ and $j = k - 1$ instead of $j = k$;

Comments

Another solution would be to add else if as shown below:

do{
    k=(i+j)/2;
    if(a[k] < x)
        i = k;
    else if (a[k] > x)
        j = k;
}while(a[k]!=x && i<j);

https://ideone.com/1kM9ib

Edit: Even this fails when array = {2,2,2,2,2,2,2,2,2} and key>3. It enters infinite loop. :(

---

what if array is not sorted then also program will fail.

---

@Priyansh Singh it is to be presumed that the array is sorted because the in the question it is mentioned that binary search is applied on the array . 

Answer 2

when input is [2 2 2 2 2 2 2 2 2 2] and search key x > 2 

i=1   j=10     k= ((1+10)/ 2)) = 5

i=5   j=10     k= ((5+10)/ 2)) = 7

i=7   j=10     k= ((7+10)/ 2)) = 8

i=8  j=10     k= ((8+10)/ 2)) = 9

i=9  j=10     k= ((9+10)/ 2)) = 9

and goes into infinite loop 

 

for correct output 

if a[k] < x then i:= k+1

else j:= k-1;