Interpolation-binary search (Q1062762)

Consider an array of n records stored so that the keys are arranged in increasing order. Using binary search, the search for a record can be performed in time O(log n), both in the average and in the worst case. If the keys are uniformly distributed, an improved expected performance can be obtained by interpolation or, for \(n<500\), by interpolation-sequential search. Namely, the search can be performed in expected time O(log log n) by interpolation search, and \((n\pi /32)^{1/2}+O(1)\) by interpolation- sequential search. Unfortunately, both techniques require O(n) time in the worst case. In this paper it is shown that it is possible to search in O(log n) time in the worst case and, if the keys are uniformly distributed, in O(log log n) time in the average. This result is achieved by interpolation- binary search, a new technique which combines 'interpolation' and 'binary' steps; thus, the proposed algorithm represents an improvement on the existing methods.