插值搜尋
![本页使用了标题或全文手工转换](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
(重定向自插值搜索)
插值搜尋 | |
---|---|
概况 | |
類別 | 搜索算法 |
資料結構 | 數组 |
复杂度 | |
平均時間複雜度 | |
最坏时间复杂度 | |
最优时间复杂度 | |
空間複雜度 | |
最佳解 | Yes |
相关变量的定义 |
插值搜尋法(Interpolation search)是利用插值公式來計算猜測搜尋鍵值的位置。搜尋方式與二分搜尋相同。 [1]
插值公式:
插值 = (設算數 - 最小數) / (最大數 - 最小數): [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 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
def interpolation_search(arr, x):
low = 0
high = len(arr) - 1
while low <= high and arr[low] <= x <= arr[high]:
mid = low + ((high - low) // (arr[high] - arr[low])) * (x - arr[low])
if arr[mid] == x:
return mid
elif arr[mid] < x:
low = mid + 1
else:
high = mid - 1
return -1
# 测试用例
arr = [10, 20, 30, 40, 50, 60, 70, 80, 90]
x = 60
result = interpolation_search(arr, x)
print(f"元素在数组中的索引为: {result}")
参考资料
- ^ 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).
|