插值搜索

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

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

插值公式:

插值 = (设算数 -­ 最小数) / (最大数 -­ 最小数): [2]

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

算法

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

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

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

时间复杂度

二分搜索在一般的情况下时间复杂度是对数时间,进行 次比较操作( 在此处是数组的元素数量, 大O记号 对数)。 [3]

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

实现

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

参考资料

  1. ^ YehYeh. 插補搜尋法(Interpolation Search). [2019-06-11]. (原始内容存档于2020-04-27). 
  2. ^ {{插值排序}}
  3. ^ {{二分搜索算法}}
  4. ^ Andersson, Arne, and Christer Mattsson. ‘Dynamic Interpolation Search in o(log log n) Time’. In Automata, Languages and Programming, edited by Andrzej Lingas, Rolf Karlsson, and Svante Carlsson, 700:15–27. Lecture Notes in Computer Science. Springer Berlin / Heidelberg, 1993. doi:10.1007/3-540-56939-1_58
  5. ^ YehYeh. 插補搜尋法(Interpolation Search). [2019-06-11]. (原始内容存档于2020-04-27).