# 线性搜索

比较次数: 0

# 算法原理

线性搜索（Linear Search）是最简单的搜索算法，它按顺序扫描列表中的每个元素，直到找到所需的元素或者搜索完整个列表。这种方法虽然简单，但对于大型数据集来说效率较低。

# 算法步骤

从列表的第一个元素开始
依次比较每个元素与要查找的值
如果找到匹配的元素，返回其索引
如果遍历完整个列表都没有找到，返回表示未找到的标记（如-1）

# 代码实现

function linearSearch(arr, target) {
  const len = arr.length;
  
  for (let i = 0; i < len; i++) {
    // 找到目标元素，返回其索引
    if (arr[i] === target) {
      return i;
    }
  }
  
  // 未找到目标元素，返回-1
  return -1;
}

// 支持自定义比较函数的版本
function linearSearchWithComparator(arr, target, comparator) {
  const len = arr.length;
  
  for (let i = 0; i < len; i++) {
    if (comparator(arr[i], target)) {
      return i;
    }
  }
  
  return -1;
}

# 复杂度分析

# 时间复杂度

最好情况：O(1)，目标元素在列表的开始位置
最坏情况：O(n)，目标元素在列表的末尾或不存在
平均情况：O(n)，需要检查一半的元素

# 空间复杂度

O(1)，只需要常量空间存储循环变量

# 算法特点

# 优点

实现简单，容易理解
适用于小规模数据
不需要数据有序
对数据结构没有特殊要求

# 缺点

时间复杂度较高
对于大规模数据效率低
不适合频繁查找操作

# 适用场景

小规模数据集
无序数据集
只需要进行一次性查找
数据集经常变化，维护有序状态成本高

# 优化方案

哨兵优化：在数组末尾添加目标值，减少边界检查
跳跃搜索：每次跳过固定步长，适用于有序数组
二分搜索：如果数据有序，可以使用更高效的二分搜索

// 使用哨兵优化的线性搜索
function sentinelLinearSearch(arr, target) {
  const len = arr.length;
  const last = arr[len - 1];  // 保存最后一个元素
  arr[len - 1] = target;      // 设置哨兵
  
  let i = 0;
  while (arr[i] !== target) {
    i++;
  }
  
  arr[len - 1] = last;  // 恢复最后一个元素
  
  if (i < len - 1 || arr[len - 1] === target) {
    return i;
  }
  return -1;
}

// 跳跃搜索
function jumpSearch(arr, target) {
  const len = arr.length;
  const step = Math.floor(Math.sqrt(len));
  
  // 找到可能包含目标值的块
  let prev = 0;
  while (arr[Math.min(step, len) - 1] < target) {
    prev = step;
    step += Math.floor(Math.sqrt(len));
    if (prev >= len) {
      return -1;
    }
  }
  
  // 在块内进行线性搜索
  while (arr[prev] < target) {
    prev++;
    if (prev === Math.min(step, len)) {
      return -1;
    }
  }
  
  if (arr[prev] === target) {
    return prev;
  }
  
  return -1;
}

# 实际应用

在小型数据库中查找记录
在未排序的数组中查找元素
在链表等只能顺序访问的数据结构中查找元素
作为其他搜索算法的基础或备选方案

← 搜索算法二分搜索 →