插值搜索

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

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

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

时间复杂度

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

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

实现

JS code: ^[5]

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