{ File: ricebinr.pas }

{ Scopo: ricerca binaria (ricorsiva) di un elemento in un vettore ordinato }

{ E` richiesta la definizione preliminare di:

const
  NumElementi = ...;

type
  TipoElemento = ...;
  TipoIndice   = 1..NumElementi;
  TipoVettore  = array [TipoIndice] of TipoElemento;

}

procedure RicercaBinaria (A    : TipoVettore;
                          n    : TipoIndice;
                          elem : TipoElemento;
                          var trovato : boolean;
                          var posiz   : TipoIndice);

{ Effettua la ricerca binaria di elem tra i primi n elementi del vettore A,
  che deve essere ordinato in ordine crescente.
  Alla fine dell'esecuzione della procedura la variabile booleana trovato e`
  TRUE se l'elemento e` presente in A, FALSE altrimenti.
  Se l'elemento e` presente, posiz contiene l'indice della componente pari
  all'elemento cercato.
  Versione ricorsiva che utilizza una procedura locale ricorsiva. }

  procedure RicercaBinariaRic (inf, sup: TipoIndice);
  { Procedura ricorsiva che effettua la ricerca nella parte fra inf e sup. }
  var
    med : integer;

  begin { RicercaBinariaRic }
    if inf <= sup then
    begin
      med := (inf + sup) div 2;
      if elem = A[med] then              { l'elemento e` stato trovato }
      begin
        trovato := TRUE;
        posiz := med
      end
      else
        if elem < A[med] then
          RicercaBinariaRic(inf, med-1)  { cerca nella parte inferiore }
        else                        
          RicercaBinariaRic(med+1, sup)  { cerca nella parte superiore }
    end
  end; { RicercaBinariaRic }

begin { RicercaBinaria }
  trovato := FALSE;
  RicercaBinariaRic(1, n)
end; { RicercaBinaria }