{ File: ricebini.pas }

{ Scopo: ricerca binaria (iterativa) 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 RicercaBinariaIter (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 iterativa. }

var
  inf, med, sup : TipoIndice;

begin { RicercaBinariaIter }
  trovato := FALSE;
  inf := 1;
  sup := n;
  
  while (inf <= sup) and (not trovato) do
  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
          sup := med-1             { cerca nella parte inferiore }
        else         
          inf := med+1             { cerca nella parte superiore }
  end
end; { RicercaBinariaIter }