program SequencialBinaria;

const MAXN = 10;
type TipoChave    = integer;
type TipoRegistro = record
                      Chave: TipoChave;
                      { outros componentes }
                    end;
     TipoIndice   = 0..MAXN;
     Tipotabela   = record
                      Item: array [TipoIndice] of TipoRegistro;
                      n   : TipoIndice;
                    end;

procedure Inicializa (var T: Tipotabela);
begin
  T.n := 0;
end; { Inicializa }

function Pesquisa (x: TipoChave; var T: Tipotabela): TipoIndice;
var i: integer;
begin
  T.Item[0].Chave := x;
  i := T.n + 1;
  repeat
    i := i - 1;
  until T.Item[i].Chave = x;
  Pesquisa := i;
end; { Pesquisa }

procedure Insere (Reg: TipoRegistro; var T: Tipotabela);
begin
  if T.n = MAXN
  then writeln('Erro: tabela cheia')
  else begin
       T.n := T.n + 1;
       T.Item[T.n] := Reg;
       end;
end; { Insere }

function Binaria (x: TipoChave; var T: Tipotabela): TipoIndice;
var i, Esq, Dir: TipoIndice;
begin
  if T.n = 0
  then Binaria := 0
  else begin
       Esq := 1; Dir := T.n;
       repeat
         i := (Esq + Dir) div 2;
         if x > T.Item[i].Chave 
	 then Esq := i+1 
	 else Dir := i-1;
       until (x = T.Item[i].Chave) or (Esq > Dir);
       if x=T.Item[i].Chave 
       then Binaria := i 
       else Binaria := 0;
       end;
end; { Binaria }

var
  T         : Tipotabela;
  reg       : TipoRegistro;
  vetor     : array [1..MAXN] of TipoChave;
  pos       : TipoIndice;
  i, j, k, n: integer;

begin
  
  Inicializa(T);
  
  { Pesquisa na Tabela Vazia }
  writeln('Pesquisa Binaria na tabela vazia');
  pos :=  Binaria(1, T);
  if pos <> 0
  then begin
       writeln('Pesquisa Falhou');
       halt;
       end;
  writeln('Pesquisa Sequencial na tabela vazia');
  pos := Pesquisa(1, T);
  if pos <> 0
  then begin
       writeln('Pesquisa Falhou');
       halt;
       end;
  
  { Insere as chaves ordenas tabela }
  for i := 1 to MAXN do
    begin
    vetor[i] := i;
    reg.Chave := vetor[i];
    Insere(reg, T);
    writeln('Inseriu: ', vetor[i]);
    end;
  
  { Pesquisa Binaria em cada chave }
  writeln('Pesquisa Binaria (chaves ordenadas)');
  for i := 1 to MAXN do
    begin
    pos := Binaria(i, T);
    if pos = 0
    then begin
         writeln('Pesquisa Falhou');
         halt;
         end
    else writeln('Registro ', i, ' na posicao: ', pos);
    end;
  
  { Permuta as chaves }
  randomize;
  for i := 1 to MAXN do
    begin
    k := 1 + random(MAXN);
    j := 1 + random(MAXN);
    n := vetor[k];
    vetor[k] := vetor[j];
    vetor[j] := n;
    end;

  { Insere as chaves na tabela }
  Inicializa(T);
  for i := 1 to MAXN do
    begin
    reg.Chave := vetor[i];
    Insere(reg, T);
    writeln('Inseriu: ', vetor[i]);
    end;
  
  { Pesquisa Sequencial em cada chave }
  writeln('Pesquisa Sequencial (chaves desordenadas)');
  for i := 1 to MAXN do
    begin
    reg.Chave := i;
    pos := Pesquisa(reg.Chave, T);
    if pos = 0
    then begin
         writeln('Pesquisa Falhou');
         halt;
         end
    else writeln('Registro ', i, ' na posicao: ', pos);
    end;
  
end. { SequencialBinaria }