线性查找

搜索算法

从头到尾逐个检查数组中的每个元素,直到找到目标值或遍历完整个数组。简单直观但效率较低,适合小型或无序数据集。

时间复杂度:最佳 O(1) | 平均 O(n) | 最差 O(n)
空间复杂度:O(1)

应用场景/前提条件

  • 适用于无序数据
  • 适合小规模数据集

算法讲解

线性查找

介绍

线性查找(Linear Search),也称为顺序查找(Sequential Search),是最简单的一种查找算法。它的工作原理是:从数据结构的第一个元素开始,按顺序依次检查每个元素,直到找到目标值或者遍历完整个数据结构。线性查找不要求数据必须是有序的,适用于各种数据集合。

算法步骤

  1. 从数据结构的第一个元素开始
  2. 将当前元素与要查找的目标值进行比较
  3. 如果当前元素等于目标值,则查找成功,返回元素的位置
  4. 如果当前元素不等于目标值,则继续检查下一个元素
  5. 重复步骤2-4,直到找到目标值或者遍历完所有元素
  6. 如果遍历完所有元素仍未找到目标值,则查找失败,返回表示失败的信息(如-1)

核心特性

  • 简单性:算法思路简单,易于实现
  • 适用性:适用于任何数据结构,不需要预先排序
  • 时间复杂度:最好情况O(1),最坏和平均情况均为O(n)
  • 空间复杂度:O(1),只需要常数级的额外空间

...