插值搜索

插值搜索法（Interpolation search）是利用插值公式来计算猜测搜索键值的位置。搜索方式与二分搜索相同。

插值公式：

插值 = (设算数 -­ 最小数) / (最大数 -­ 最小数)：

搜索键值 = left + parseInt( ( key - data ) / ( data - data ) )*( right - left ) )

插值搜索之算法与二分搜索算法几乎完全相同，差别在：

二分搜索法：猜测键值在中间位置(middle)

插值搜索法：用插值公式计算键值位置

二分搜索在一般的情况下时间复杂度是对数时间，进行${\displaystyle O(\log <!--\; \; -->n)}$次比较操作（${\displaystyle n}$在此处是数组的元素数量，${\displaystyle O}$是大O记号，${\displaystyle \log }$是对数）。

插值搜索的最坏时间复杂度是${\displaystyle O(n)}$，平均进行${\displaystyle O(\log <!--\; \; -->(\log <!--\; \; -->n))}$次比较操作。因为用插值公式计算搜索键值，能使搜索范围比二分法更快缩小。所以除非输入数据数量很少，否则插值搜索比二分搜索与线性搜索更快，但数组必须事先被排序。无论对任何大小的输入数据，插值搜索算法使用的空间复杂度一样是${\displaystyle O(1)}$。

JS code: