搜索算法深入
实现并分析线性搜索、二分搜索和哈希搜索及其权衡。
你将学到
- 线性搜索:在无序数据上为 O(n)
- 二分搜索:在有序数据上为 O(log n)
- 均匀分布数据的插值搜索
- 何时使用每种搜索策略
概念讲解
搜索算法深入
搜索是在集合中查找目标值的问题。你选择的算法关键取决于数据是否有序以及搜索频率。
线性搜索
线性搜索逐个检查每个元素。适用于任何数据,运行时间为 O(n)。对无序数据是最优的。
二分搜索
二分搜索需要有序数据。反复将搜索范围减半,时间为 O(log n)。当 n = 1,000,000 时,约需 20 次比较而非 1,000,000 次。关键洞察:每次比较排除一半剩余元素。
插值搜索
当数据有序且均匀分布时,插值搜索估计目标位置(就像在电话簿中查找名字)。在均匀数据上达到 O(log log n),但在聚集数据上退化为 O(n)。
哈希搜索
哈希表提供 O(1) 平均查找,但需要 O(n) 额外空间。当反复搜索且能负担内存时是最佳选择。权衡:哈希表不支持有序遍历。
选择策略
无序单次搜索用线性;有序反复搜索用二分;反复查找用哈希表;有序均匀用插值。
示例代码
// Linear search - works on any array
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}
// Binary search - requires sorted array
function binarySearch(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (arr[mid] === target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
const sorted = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
console.log('Linear:', linearSearch(sorted, 13));
console.log('Binary:', binarySearch(sorted, 13));
console.log('Not found:', binarySearch(sorted, 14));
线性搜索扫描每个元素。二分搜索每次迭代将范围减半,要求数组有序。两者都返回索引或未找到时返回 -1。
动手试一试
- JSON Formatter
在格式化的 JSON 结构中搜索,理解搜索如何应用于嵌套数据。
常见错误
错误写法
在无序数据上使用二分搜索。
正确做法
二分搜索需要有序数据。如果数组未排序,减半逻辑无效,会得到错误结果。
错误写法
中间值计算的整数溢出。
正确做法
使用 (lo + hi) >> 1 或 lo + ((hi - lo) >> 1) 而非 (lo + hi) / 2,以避免定长整数语言的溢出。
查阅不认识的术语
新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。
动手做项目
通过引导式项目应用所学,含起始代码与解决方案。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。