Skip to content

查找算法

一句话解释

查找算法在数据结构中定位目标值的位置(或判断其是否存在)。

用大白话说

查找算法在数据结构中定位某个特定值。最简单的是线性查找:逐个检查每个元素——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)。

相关术语

相关资源

相关课程

解读错误信息

用大白话解释常见错误——什么意思、为什么发生、如何修复。

查看错误

← 返回术语表