Program Algorithm;

{ Binary search.
  Algorithm B on page 407 of "The Art of Computer Programming"
  volume 3 / "Sorting and Searching" by Donald E. Knuth. }

const
  N = 70;
  R = 5;

var
  m, g : word;
  rij : array[1..N] of word;
  ok : boolean;

function BinSearch : boolean;

var
  l, u, i : word;

begin
  l := 1;
  u := N;

  repeat

    if u < l then
    begin
      BinSearch := false;
      Exit;
    end;
    i := (l + u) shr 1;
    if g < rij[i] then
    begin
      u := i - 1;
      Continue;
    end;
    if g > rij[i] then
    begin
      l := i + 1;
      Continue;
    end;
    if g = rij[i] then
    begin
      BinSearch := true;
      Exit;
    end;

  until false;

end;

begin
  m := 1;
  rij[1] := Random(R) + 5;
  for m := 2 to N do
  begin
    Write(rij[m-1],' ');
    rij[m] := rij[m-1] + Random(R);
  end;
  Writeln(rij[N]);

  g := 2; { special }
  for m := 1 to 15 do
  begin
    ok := BinSearch;
    if ok then
      Writeln(g,' : found')
    else
      Writeln(g,' : not found');
    g := Random(N);
  end;
end.