• An algorithm for searching for a key in an array that has been ordered by numerical values assigned to the keys (key values). Interpolation search was first described in 1957 by W.W. Peterson. It resembles the method by which people search a telephone directory for a name (the key value by which the book’s entries are ordered): In each step the algorithm calculates where in the remaining search space the sought item might be, based on the key values at the bounds of the search space and the value of the sought key, usually via a linear interpolation. The key value actually found at this estimated position is then compared to the key value being sought. If it is not equal, then depending on the comparison, the remaining search space is reduced to the part before or after the estimated position. This method works if calculations on the size of differences between key values are sensible. ← Wikipedia

1. Previous term: Interpolation
2. Next term: Intersection Observer
3. Random term: Confidentiality, integrity, and availability