数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时装设计
法学用 JavaScript 实现块搜索
块搜索
就像二分查找，块搜索也是一个用于排序数组的搜索算法。基本思想是通过固定步进或跳过某些元素而不是搜索所有元素来检查更少的元素（比线性搜索）。
例如
假设我们有一个长度为 n 的数组 arr 和大小为 m 的块（要跳过）。然后我们从索引 arr[0]、arr[m]、arr[2 * m]、...、arr[k * m] 等进行搜索。
一旦我们找到区间 arr[k * m] < x < arr[(k+1) * m]，我们就从索引 k * m 开始执行线性搜索操作以找到元素 x。
该算法的时间复杂度为 -
O(√n)
示例
以下为代码 -
const arr = [1, 4, 6, 7, 9, 12, 15, 16, 17, 23, 25, 26, 27, 31];
const target = 25;
const blockSearch = (arr = [], target) => {
let { length: len } = arr;
let step = Math.floor(Math.sqrt(len));
let blockStart = 0
let currentStep = step;
while (arr[Math.min(currentStep, len) - 1] < target) {
blockStart = currentStep;
currentStep += step;
if (blockStart >= len)
return -1;
}
while (arr[blockStart] < target){
blockStart++;
if (blockStart == Math.min(currentStep, len))
return -1;
}
if (arr[blockStart] == target)
return blockStart
else
return -1;
};
console.log(blockSearch(arr, target));输出
以下是控制台上的输出 -
10
更新时间： 11-Dec-2020
211 次查看
广告