Flexible interpolated-binary search over sorted sets

We revisit the classical algorithms for searching over sorted sets and introduce a new algorithm, called adaptive search, that combines the good features of Interpolation search and those of Binary search. W.r.t. Insertion sort, only a constant number of extra comparisons is introduced. Yet, under several relevant input data distributions our algorithm shows average case cost comparable to that of Interpolation Search, i.e., O(log log n) while the worst case cost is always in O(log n), as with Binary search. This result compares well with the traditional result of Santoro and Sidney Interpolation-Binary Search and the recent approach of Demaine et al. on searching non-independent data.