顺序搜索（Sequential Search）
【摘要】 顺序搜索（Sequential Search）
1.顺序搜索（Sequential Search）
认识
顺序搜索也称为线性搜索（Linear Search）。它的基本思想是从数据结构的一端开始，逐个检查每个元素，直到找到目标元素或检查完所有元素。
function sequentialSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i;
}
}
return -1;
};
const arr = [4, 3, 6, 2, 5, 7, 9, 8, 1]
console.log(sequentialSearch(arr, 8)) // 7
Javascript顺序搜索实现
基础实现
基础实现比较好写，就是一个小标
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>顺序搜索 Sequential Search</title>
</head>
<body>
<script>
// 1 顺序搜索
function SequentialSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
// 功能测试
const arr = [1, 4, 3, 6, 2, 5, 7, 9, 8];
let target = 2;
let result = SequentialSearch(arr, target);
console.log(`元素 ${target} 在数组中的索引是 ${result}`);
</script>
</body>
</html>
哨兵模式（Sentinel Pattern）优化
针对哨兵模式进行优化
也就是将上面循环中的判断条件进行减少为一个
【哨兵模式】将目标值作为哨兵放在了数组的末尾，确保循环一定会终止
// 需要同时检查两个条件:
// 1. arr[i] === target - 找到目标元素
// 2. i < arr.length - 确保没有超出数组范围
实现
// 2-优化-哨兵模式
function SequentialSearch(arr, target) {
// 如果数组为空，直接返回-1
if (arr.length == 0) {
return -1
}
// 保存最后一个元素
const last = arr[arr.length - 1];
arr[arr.length - 1] = target; // 将最后一个元素设为哨兵
let i = 0;
while (arr[i] !== target) {
i++
}
// 恢复最后一个元素
arr[arr.length - 1] = last;
// 如果找到的位置不是最后一个元素，或者是最后一个元素且值匹配
if (i < arr.length - 1 || arr[arr.length - 1] === target){
return i
}
return -1;
}
双向迭代优化
双向迭代顺序搜索，同时从左和右开始进行搜索
/**
* 3-双向迭代顺序搜索（从前和从后同时搜索）
* @param {Array} arr - 待搜索的数组
* @param {*} target - 要查找的目标元素
* @return {number} 目标元素的索引，如果未找到则返回-1
*/
function iterativeBidirectionalSearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
// 从前向后检查
if (arr[left] === target) {
return left;
}
// 从后向前检查
if (arr[right] === target) {
return right;
}
left++;
right--;
}
return -1;
}
概率优化–暂时没理解
/**
* 4-基于概率的迭代顺序搜索（高频元素优先）
* @param {Array} arr - 待搜索的数组
* @param {*} target - 要查找的目标元素
* @param {Object} frequencyMap - 可选的频率映射表
* @return {number} 目标元素的索引，如果未找到则返回-1
*/
function iterativeProbabilisticSearch(arr, target, frequencyMap = null) {
// 如果没有提供频率映射表，则创建一个
if (!frequencyMap) {
frequencyMap = {};
for (const item of arr) {
frequencyMap[item] = (frequencyMap[item] || 0) + 1;
}
}
// 创建一个按频率排序的索引数组
const indices = Array.from({ length: arr.length }, (_, i) => i);
indices.sort((a, b) =>
(frequencyMap[arr[b]] || 0) - (frequencyMap[arr[a]] || 0)
);
// 按照排序后的索引顺序搜索
for (const i of indices) {
if (arr[i] === target) {
return i;
}
}
return -1;
}
// 使用示例
const myList = [4, 2, 7, 1, 9, 5, 7, 2, 7];
console.log(iterativeProbabilisticSearch(myList, 7)); // 输出: 2
缓存优化
下面的优化非常的简单，但是符合V8引擎的设计
每次循环迭代都需要访问arr.length属性调整为 只在循环开始前访问一次arr.length并将其存储在局部变量length中
JavaScript引擎（如V8）对局部变量的访问速度远快于对象属性访问。这是因为：
- 局部变量存储在寄存器或栈上，访问速度快
- 对象属性存储在堆上，需要通过属性查找机制访问，速度较慢
这种局部变量的访问由于存储在在寄存器或栈上 访问速度明显大于存储在堆上的对象属性，以前我还一直坚持不增加多余局部变量呢
function iterativeCachedSearch(arr, target) {
const length = arr.length; // 缓存数组长度
for (let i = 0; i < length; i++) {
if (arr[i] === target) {
return i;
}
}
return -1;
}
// 使用示例
const myList = [4, 2, 7, 1, 9, 5];
console.log(iterativeCachedSearch(myList, 7)); // 输出: 2
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）