Three methods of locating a record in a static, ordered file are compared under different assumptions about the statistical distribution from which the keys are drawn. The methods, specifically, are the interpolation search by Perl et al. [1], the robust search by Burton and Lewis [2], and a new method proposed by the authors. Pegasus superlinear root finding method for a continuous function [3] forms the basis for the new search method. The experimental results show that:

• (1) The time complexity for these methods has a growth rate of lg lg (N), except for Perl’s method with the key values following either gamma or exponential distribution.

• (2) Under the condition that the key values follow uniform distribution, Perl’s method is the best. Otherwise, the proposed scheme based on the Pegasus method is better than the robust and the interpolation search methods.