2,741 views

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;


isn't this will also effect the loop (i >= j); i should be greater than j. ??
I am not getting the until part here.

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$;

edited

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 .

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;

by