8.2.5 Interpolation Search

Sometimes, telephone directories, like dictionaries and encyclopedias, have tabs so that users can flip open the book to the beginning of the section containing entries with a specific first letter and gauge whether to search toward the front, middle, or back pages of the section. The tabs have been inserted or interpolated within the data to guide the search. This represents a generalization of the binary search called the interpolation search. The topic will not be pursued in detail, but note that this technique allows the elimination of greater fractions of the remaining names than does a binary search. Not surprisingly, this tends to reduce the execution time.