// Prof. carlos Maziero, DINF-UFPR, Maio de 2016

program buscas ;

const
  SIZE = 1000 ;

type
  vetor = array [1..SIZE] of integer ;

//-------------------------------------------------------------------
// Leitura de um vetor V com N posicoes

procedure leitura (var v: vetor; var n: integer) ;
var
  i : integer ;

begin
  repeat
    write ('Numero de elementos: ') ;
    read (n) ;
  until (n > 0) AND (n <= SIZE) ;

  for i := 1 to n do		// lê o vetor
  begin
    write ('V[', i,']: ') ;
    read (v[i]) ;
  end ;
  writeln ;
end ;

//-------------------------------------------------------------------
// Escrita na tela de um vetor V com N posições

procedure escrita (v: vetor; n: integer) ;
var
  i : integer ;

begin
  for i := 1 to n do		// escreve o vetor
    write (v[i]:5) ;
  writeln ;
end ;

//-------------------------------------------------------------------
// troca dois inteiros i1 e i2 entre si

procedure troca (var i1, i2: integer) ;
var
  aux : integer ;
begin
  aux := i1 ;
  i1  := i2 ;
  i2  := aux ;
end ;

//-------------------------------------------------------------------
// ordena um vetor V com N posições usando o método da seleção

procedure ordena (var v: vetor; n: integer) ;
var
  i, posmenor, postroca : integer ;

begin
  for postroca := 1 to n-1 do
  begin
    posmenor := postroca ;	// menor é o primeiro (do vetor restante)
    for i := postroca to n do	// verifica se há alguém menor
      if v[i] < v[posmenor] then
        posmenor := i ;
    troca (v[posmenor], v[postroca]) ;
  end ;
end;

//---------------------------------------------------------

// busca em vetor não-ordenado, varredura completa
function busca1 (val: integer; v: vetor; tam: integer) : integer ;
var
  i, pos : integer ;
begin
  pos := 0 ;
  for i:= 1 to tam do
    if v[i] = val then
      pos := i ;
  busca1 := pos ;
end ;

// busca em vetor não-ordenado, para ao encontrar
function busca2 (val: integer; v: vetor; tam: integer) : integer ;
var
  i: integer ;
begin
  i := 1 ;
  while (i <= tam) AND (v[i] <> val) do
    i := i + 1 ;

  if i <= tam then
    busca2 := i
  else
   busca2 := 0 ;
end ;

// busca em vetor não-ordenado, para ao encontrar, com sentinela
function busca3 (val: integer; v: vetor; tam: integer) : integer ;
var
  i: integer ;
begin
  tam := tam + 1 ;
  v[tam] := val ;

  i := 1 ;
  while (v[i] <> val) do
    i := i + 1 ;

  if i < tam then
    busca3 := i
  else
   busca3 := 0 ;
end ;

// busca em vetor ordenado, para ao encontrar ou passar do valor
function busca4 (val: integer; v: vetor; tam: integer) : integer ;
var
  i: integer ;
begin
  i := 1 ;
  while (i <= tam) AND (val > v[i]) do
    i := i + 1 ;

  if i > tam then
    busca4 := 0
  else
   if val = v[i] then
     busca4 := i
   else
     busca4 := 0 ;
end ;

// busca binária em vetor ordenado
function busca5 (val: integer; v: vetor; tam: integer) : integer ;
var
  inicio, final, metade : integer ;

begin
  inicio := 1 ;
  final := tam ;

  metade := (inicio + final) div 2 ;

  while (v[metade] <> val) AND (inicio <> final) do
  begin
    if (v[metade] < val) then
      inicio := metade + 1
    else
      final := metade ;
    metade := (inicio + final) div 2 ;
  end ;

  if val = v[metade] then
     busca5 := metade
  else
     busca5 := 0 ;
end ;

//-------------------------------------------------------------------
// Programa principal

var
  vet : vetor ;
  num : integer ;

begin
  leitura (vet, num) ;
  escrita (vet, num) ;
  writeln ('Posicao de 21: ', busca1 (21, vet, num)) ;
  writeln ('Posicao de 21: ', busca2 (21, vet, num)) ;
  writeln ('Posicao de 21: ', busca3 (21, vet, num)) ;
  ordena  (vet, num) ;
  write ('Vet ord: ') ;
  escrita (vet, num) ;
  writeln ('Posicao de 21: ', busca4 (21, vet, num)) ;
  writeln ('Posicao de 21: ', busca5 (21, vet, num)) ;
  writeln ('Posicao de 90: ', busca5 (90, vet, num)) ;
end.