查找算法
一句话解释
查找算法在数据结构中定位目标值的位置(或判断其是否存在)。
用大白话说
查找算法在数据结构中定位某个特定值。最简单的是线性查找:逐个检查每个元素——O(n) 时间,适用于任何列表。对已排序数据,二分查找快得多:反复将查找范围减半——O(log n) 时间。查找方式取决于数据与查找频率。若对无序数据只查一次,线性查找即可。若要多次查找,先排序再用二分查找,或建哈希表实现 O(1) 查找。对图,则用广度优先或深度优先搜索寻找相连节点或路径。查找与数据结构紧密相关:数组支持下标访问,链表需遍历,树支持递归下降,哈希表支持按键直查。事先选对结构往往决定了查找速度。
示例
javascript
// 二分查找——需要已排序数组
function binarySearch(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
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];
console.log(binarySearch(sorted, 7)); // 3(下标)
console.log(binarySearch(sorted, 4)); // -1(未找到)二分查找将中间元素与目标比较,每步淘汰一半范围。在已排序输入上为 O(log n)。
相关术语
相关资源
相关课程
- 算法
学习查找算法。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。