插值搜索
插值搜索法(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
参考资料
- ^ YehYeh. 插補搜尋法(Interpolation Search). [2019-06-11]. (原始内容存档于2020-04-27).
- ^ {{插值排序}}
- ^ {{二分搜索算法}}
- ^ 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
- ^ YehYeh. 插補搜尋法(Interpolation Search). [2019-06-11]. (原始内容存档于2020-04-27).