数据结构
网络
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 次
广告