{ 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 }