Editing Interpolation search (section)

{{short description|Searching algorithm}}
{{more citations needed|date=September 2017}}

'''Interpolation search''' is an [[algorithm]] for [[Search algorithm|searching]] for a key in an array that has been [[Collation|ordered]] by numerical values assigned to the keys (''key values''). It was first described by W. W. Peterson in 1957.<ref>{{cite journal|author=W. W. Peterson|year=1957|title=Addressing for Random-Access Storage|journal=IBM J. Res. Dev.|volume=1|issue=2|pages=130–146|doi=10.1147/rd.12.0130}}</ref> Interpolation search 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 [[Mathematical optimization#Optimization problems|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 will only work if calculations on the size of differences between key values are sensible.

{{use dmy dates|date=February 2022}}
{{Infobox algorithm
|class=[[Search algorithm]]
|image=Interpolation sort.gif
|caption=Visualization of the interpolation search algorithm in which 24 is the target value.
|data=[[array data structure|Array]]
|time=[[big O notation#Orders of common functions|''O''(''n'')]]
|space = [[big O notation#Orders of common functions|''O''(1)]]
|best-time=[[big O notation#Orders of common functions|''O''(1)]]
|average-time=[[big O notation#Orders of common functions|''O''(log(log(''n'')))]]<ref>{{cite web|author=Simon Yuan|title=Understanding The Complexity Of Interpolation Search, Seminar Advanced Algorithms and Data Structures|url= https://cadmo.ethz.ch/education/lectures/HS18/SAADS/reports/17.pdf}}</ref>
|optimal=Yes
}}

By comparison, [[binary search]] always chooses the middle of the remaining search space, discarding one half or the other, depending on the comparison between the key found at the estimated position and the key sought — it does not require numerical values for the keys, just a total order on them. The remaining search space is reduced to the part before or after the estimated position. The [[linear search]] uses equality only as it compares elements one-by-one from the start, ignoring any sorting.

On average the interpolation search makes about log(log(''n'')) comparisons (if the elements are uniformly distributed), where ''n'' is the number of elements to be searched. In the worst case (for instance where the numerical values of the keys increase exponentially) it can make up to [[Big O notation|O]](''n'') comparisons.

In interpolation-sequential search, interpolation is used to find an item near the one being searched for, then [[linear search]] is used to find the exact item.