Physical Sciences and Mathematics Commons^™

Experiments With The Gap Variation Of Interpolation Search For Semi Uniform Distributed Alphabetic Files, Jatin M. Bhavsar

Theses

There are various techniques for searching a data from a data base. One of them is interpolation search. It works on uniformly distributed and sorted numerical tables and considered to be one of the fastest methods. On an average this method takes 'lg lg n'

Burton and Lewis [BL] shows the inefficiency of interpolation sarch for an alphabetic table whose distribution is not known or non-uniform. They introduce GAP variations of interpolation search to compare the inefficiency. However another approach to a non-uniform is to apply the cumulative distribution function F which transfer a non-uniform distribution to uniform one, for …