查看“︁插值搜尋”︁的源代码

{{NoteTA
|G1=IT
|1=zh-tw:插值搜尋演算法;zh-cn:插值搜索算法;
}}
{{Infobox Algorithm
|class=[[搜索算法]]

|caption=
|data=[[數组]]
|time=<math> O(n) </math>
|space=<math> O(1) </math>

|best-time=<math> O(1) </math>
|average-time=<math> O(\log (\log n)) </math>
|optimal=Yes
}}

'''插值搜尋法'''（Interpolation search）是利用插值公式來計算猜測搜尋鍵值的位置。搜尋方式與[[二分搜尋]]相同。
<ref name="InterpolationSearch">{{cite web |url=http://notepad.yehyeh.net/Content/Algorithm/Search/InterpolationSearch/InterpolationSearch.php |title=插補搜尋法(Interpolation Search) |author=YehYeh |access-date=2019-06-11 |archive-date=2020-04-27 |archive-url=https://web.archive.org/web/20200427191801/http://notepad.yehyeh.net/Content/Algorithm/Search/InterpolationSearch/InterpolationSearch.php |dead-url=no }}</ref> 

插值公式：

插值 = (設算數 - 最小數) / (最大數 - 最小數)：
<ref name="插值排序">{{[[插值排序]]}}</ref>

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

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

二分搜尋法：猜測鍵值在中間位置(middle)

插值搜尋法：用插值公式計算鍵值位置

===時間複雜度===
[[二分搜尋]]在一般的情況下時間複雜度是對數時間，進行<math>O(\log n)</math>次比較操作（<math>n</math>在此處是數組的元素數量，<math >O</math>是[[大O符號|大O記號]]，<math>\log</math>是[[對數]]）。
<ref name="二分搜尋">{{[[二分搜尋演算法]]}}</ref>

插值搜尋的最壞時間複雜度是<math>O(n)</math>，平均進行<math>O(\log(\log n))</math>次比較操作<ref>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}}</ref>。因為用插值公式計算搜尋鍵值，能使搜尋範圍比二分法更快縮小。所以除非輸入數據數量很少，否則插值搜尋比二分搜尋與線性搜尋更快，但數組必須事先被排序。無論對任何大小的輸入數據，插值搜尋演算法使用的空間複雜度一樣是<math>O(1)</math>。

===實作===
JS code:
<ref name="YehYeh_code">{{cite web |url=http://notepad.yehyeh.net/Content/Algorithm/Search/InterpolationSearch/InterpolationSearch.php |title=插補搜尋法(Interpolation Search) |author=YehYeh. |access-date=2019-06-11 |archive-date=2020-04-27 |archive-url=https://web.archive.org/web/20200427191801/http://notepad.yehyeh.net/Content/Algorithm/Search/InterpolationSearch/InterpolationSearch.php |dead-url=no }}</ref>

<syntaxhighlight lang="javascript">
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)
</syntaxhighlight>

===[[Julia (程式語言)]]===
<syntaxhighlight lang="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
</syntaxhighlight>[[Python]]3<syntaxhighlight lang="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}")
</syntaxhighlight>

==参考资料==
{{reflist}}

{{算法}}

[[Category:搜尋演算法]]