插補搜尋(Interpolation Search)演算法又稱為內插搜尋演算法,是二元搜尋(Binary Search)演算法的變體。這套演算法可以在已排序好的序列中根據資料的預測線或近似線來進行高效率的搜尋,近似線愈精準,搜尋的效率就愈高。
依照公式程式碼如下:
function interpolationSearch(arr, key) {
let start = 0;
let end = arr.length - 1;
while (end >= start) {
let m = Math.floor((key - arr[start]) * (end - start) / (arr[end] - arr[start]) + start);
if (m > end || m < start) {
break;
}
if (arr[m] === key) {
return m;
} else {
if (key > arr[m]) {
start = m + 1;
} else {
end = m - 1;
}
}
}
return -1;
}
const arr=[0,1,2,3,4,5,6,7,8,9];
console.log(interpolationSearch(arr,3));