插值搜索

插值搜索
概况
类别	搜索算法
数据结构	数组
复杂度
平均时间复杂度	$O(\log(\log n))$
最坏时间复杂度	$O(n)$
最优时间复杂度	$O(1)$
空间复杂度	$O(1)$
最佳解	Yes
相关变量的定义

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

插值公式：

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

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

算法

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

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

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

时间复杂度

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

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