插值搜索

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

插值公式：

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

搜索键值 = left + parseInt( ( key - data[left] ) / ( data[right] - data[left] ) )*( 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:

var interpolationSearch = function(data, key){
    var left = 0;
    var right = data.length - 1;
    var m = 0;
    while(left <= right){
        var m = parseInt((right - left)*(key - data[left])/(data[right] - data[left])) + left;
        if( m < left || m > right)
            break;
        if(key < data[m])
            right = m - 1;
        else if(key > data[m])
            left = m + 1;
        else
            return m;           
    }
    return -1;
};

//執行
var data = getRandomData();
quickSort(data, 0, data.length-1);
interpolationSearch(data, 5);        // (data, key)

Julia (编程语言)

# Julia Sample : InterSearch
function InterSearch(A,key)
    left,right,m = 1, length(A), 1
    while(left<=right)
        m=floor(Int,((right-left)*(key-A[left])/(A[right]-A[left])+left))

        if (m<left)||(m>right)
            break
        end

        if key<A[m]
            right=m-1
        elseif key>A[m]
            left=m+1
        else
            return m
        end

    end
    return -1
end

# Main Code
A = [1,3,16,31,43,354,586]   # Already Arrange
println(A)                   # Original Array
println(InterSearch(A,43))   # Interpolation Search Array
println(InterSearch(A,354))  # Interpolation Search Array
println(InterSearch(A,3))    # Interpolation Search Array

原文地址：
https://zh.wikipedia.org/wiki/%E6%8F%92%E5%80%BC%E6%90%9C%E5%B0%8B

在知识共享 署名-相同方式共享 3.0协议之条款下提供