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

插值公式：

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

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

目录 1 算法 1.1 时间复杂度 1.2 实现 1.3 Julia (编程语言) 2 参考资料 算法 插值搜索之算法与二分搜索算法几乎完全相同，差别在：

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

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

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

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

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: