Skip to content

顺序查找

· 2 min

基础知识

顺序查找，对应的英文为 Sequential Search，又被称之为 线性查找，是一种最简单的查找算法。它的核心思想是从数组的第一个元素开始，逐个检查每个元素，直到找到目标元素或者遍历完整个数组。顺序查找的工作方式非常直观：

  1. 从数组的第一个元素开始，依次检查每个元素。
  2. 如果当前元素与目标值相等，查找成功，返回元素的索引。
  3. 如果当前元素与目标值不相等，则继续检查下一个元素。
  4. 如果遍历完整个数组都没有找到目标值，则查找失败，返回一个表示失败的标识（例如 -1）。
function search(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i
    }
  }
  // 说明整个数组遍历完了，但是没有一次进入 if
  // 说明不存在
  return -1
}


const arr = [10, 20, 30, 40, 50]
const target = 30
const result = search(arr, target)
console.log(result) // 2

时间复杂度

顺序查找的时间复杂度为 O(n)，其中 n 是数组的元素个数。最坏情况下，算法需要检查每一个元素，直到找到目标值或遍历完整个数组。

空间复杂度

顺序查找的空间复杂度为 O(1)，因为算法只需要常量级的空间来存储一些辅助变量（如索引）。不会随着 n 的增长辅助空间有任何的变化。

顺序查找的优缺点