 Interpolation search

Interpolation search is an algorithm for searching for a key in an array that has been ordered by numerical values assigned to the keys ("key values").It was first described by W. W. Peterson in 1957.