Interpolation search


function search( key : typekey; var r : dataarray ) : integer; var high, j, low : integer; begin low := 1; high := n; while (r[high].k >= key) and (key > r[low].k) do begin j := trunc( (key-r[low].k) / (r[high].k-r[low].k) * (high-low) ) + low; if key > r[j].k then low := j+1 else if key < r[j].k then high := j-1 else low := j end; if r[low].k = key then search := low {*** found(r[low]) ***} else search := -1; {*** notfound(key) ***} end;

Pascal source (322.srch.p)



© Addison-Wesley Publishing Co. Inc.