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

插值公式：

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

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

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

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

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

時間複雜度
二分搜尋在一般的情況下時間複雜度是對數時間，進行O(\log n)次比較操作（n在此處是數組的元素數量，O是大O記號，\log是對數）。

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

實作
C code:

#include

int InterSearch(int A[], int length, int key)
{
int left = 0, right = length - 1, m;
while (left right)
break;
if (key A[m])
left = m + 1;
else
return m;
}
if (A[left] == key)
return left;
return -1;
}

int main()
{
int A[] = { 1, 3, 16, 31, 43, 354, 586 };
int length = sizeof(A) / sizeof(A[0]);

printf("Index of 43: %d\n", InterSearch(A, length, 43));
printf("Index of 354: %d\n", InterSearch(A, length, 354));
printf("Index of 3: %d\n", InterSearch(A, length, 3));

return 0;
}

JS code:

var interpolationSearch = function(data, key){
var left = 0;
var right = data.length - 1;
var m = 0;
while(left right)
break;
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(leftright)
break
end

if keyA[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

参考资料