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