資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究JavaScript 中的插值搜尋
插值搜尋
插值搜尋是一種演算法，用於在一個已按分配給鍵（鍵值）的數值排序的陣列中搜索鍵。
例如
假設我們有一個 n 個均勻分佈的值的已排序陣列 arr[]，我們需要編寫一個函式來在陣列中搜索一個特定的元素 target。
它執行以下操作來查詢位置 −
// 公式的原理是當待查詢元素接近 arr[hi] 時
// 返回一個較高的 pos 值。當待查詢元素接近 arr[lo] 時
// 返回一個較小的值
pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[Lo]))
鍵 −
arr[] - 需要在其中搜索元素的陣列
x - 要查詢的元素
lo - arr[] 中的起始索引
hi - arr[] 中的結束索引
我們需要編寫一個 JavaScript 函式，它將一個數字陣列作為第一個引數，並將搜尋目標作為第二個引數。
該函式應利用插值搜尋演算法在陣列中搜索目標。
示例
以下是程式碼 −
const arr = [1, 4, 6, 7, 9, 12, 15, 16, 17, 23, 25, 26, 27, 31];
const target = 25;
const interpolationSearch = (arr = [], target) => {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const rangeDelta = arr[right] - arr[left];
const indexDelta = right - left;
const valueDelta = target - arr[left];
if (valueDelta < 0) {
return -1;
}
if (!rangeDelta) {
return arr[left] === target ? left : -1;
}
const middleIndex = left + Math.floor((valueDelta * indexDelta) / rangeDelta);
if (arr[middleIndex] === target) {
return middleIndex;
}
if (arr[middleIndex] < target) {
left = middleIndex + 1;
} else {
right = middleIndex - 1;
}
};
return -1;
};
console.log(interpolationSearch(arr, target));輸出
以下是控制檯上的輸出 -
10
更新於： 11 December 2020
瀏覽 565 次
廣告