retagged by
3,420 views
24 votes
24 votes

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;
retagged by

2 Answers

Best answer
34 votes
34 votes

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 by
10 votes
10 votes

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;

  

Related questions

55 votes
55 votes
8 answers
1
Kathleen asked Oct 9, 2014
31,359 views
The average number of key comparisons required for a successful search for sequential search on $n$ items is$\frac{n}{2}$$\frac{n-1}{2}$$\frac{n+1}{2}$None of the above
26 votes
26 votes
1 answer
3
Kathleen asked Oct 9, 2014
5,110 views
A complete, undirected, weighted graph $G$ is given on the vertex $\{0, 1,\dots, n -1\}$ for any fixed ‘n’. Draw the minimum spanning tree of $G$ ifthe weight of the ...