插值搜尋

插值搜尋
概况
類別	搜索算法
資料結構	數组
复杂度
平均時間複雜度	${\displaystyle O(\log(\log n))}$
最坏时间复杂度	${\displaystyle O(n)}$
最优时间复杂度	${\displaystyle O(1)}$
空間複雜度	${\displaystyle O(1)}$
最佳解	Yes
相关变量的定义

插值搜尋法（Interpolation search）是利用插值公式來計算猜測搜尋鍵值的位置。搜尋方式與二分搜尋相同。 [1]

插值公式：

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

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

演算法

插值搜尋之演算法與二分搜尋演算法幾乎完全相同，差別在：

二分搜尋法：猜測鍵值在中間位置(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

Python3

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}")

参考资料

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）.