线性查找

线性查找从数组开头检查每个元素，遇到目标就返回下标。输入不需要排序。最坏情况下要检查全部 n 个元素，时间复杂度为 O(n)。

在一份未排序的名单里找名字，只能从头往后看。位置不能告诉你值的大小，检查中间元素也无法排除半份名单。线性查找不依赖输入结构，代价是最坏情况下必须读完整个数组。

线性查找如何工作

让游标 i 从 0 走到 n − 1，每次比较 nums[i] 与目标。相等就返回 i 并停止，不再访问后面的元素；不相等就排除当前位置，让游标右移一格。

如果走到末尾仍未匹配，返回 −1。提前返回决定了两个性质：只读取首个匹配位置之前的元素，并返回第一次出现的下标。

输入可以有序、逆序或打乱，算法都能查找。排列改变后，目标的位置和所需比较次数可能变化，但不影响正确性。

线性查找逐步演示

默认输入为 nums = [42, 17, 8, 91, 23, 4, 56, 30]，目标为 target = 23。

1. i = 0：nums[0] = 42，与 23 不相等，继续。
2. i = 1：nums[1] = 17，不相等，继续。
3. i = 2：nums[2] = 8，不相等，继续。
4. i = 3：nums[3] = 91，不相等，继续。
5. i = 4：nums[4] = 23，匹配，返回下标 4。

共比较五次。后面的 4, 56, 30 没有被检查，因为命中后已经返回。

动画中，i 每次右移一格。比较中的单元格显示为琥珀色，排除的单元格变淡。命中位置变绿，右侧未访问的单元格保持原状。变淡区域对应本次查找实际走过的范围。

时间与空间复杂度

首次匹配在下标 k 时，需要 k + 1 次比较；未找到时需要 n 次。播放器显示的比较次数就按这个规则增加。额外空间为 O(1)，只需一个下标，不建辅助结构。

何时使用线性查找

未排序数据的一次性查询、小集合，以及只能顺序访问的结构，都适合线性查找。链表没有数组式的随机访问，不能直接获得数组二分查找的 O(log n) 查询时间。

如果同一集合要被反复查询，可以先用 O(n) 时间建立哈希集合，再以平均 O(1) 时间判断是否存在。已有序的数组适合二分查找，时间为 O(log n)。选择时也要计算预处理的成本，不能只比较单次查询。

边界情况

• 空数组：循环体不执行，不做比较，返回 −1。这是代码的行为；交互播放器要求至少五个元素。
• 目标在首位：一次比较就返回，是 O(1) 的最好情况。
• 目标在末位或不存在：两者都比较 n 次，区别只在最后是否命中。
• 目标重复出现：返回第一次出现的下标，不再检查后面的副本。

常见错误

• 命中后没有提前返回：如果只更新记录而继续扫描，可能返回最后一次出现的位置，而且无论目标在哪都要比较 n 次。
• 认为输入必须排序：线性查找不需要排序。为一次查询先排序，通常增加了工作；如果数据已有序并且需要更快查询，可选二分查找。
• 对频繁查询反复扫描：单次扫描的成本不高，查询次数增加后会累积。考虑哈希集合或排序后的二分查找。
• 漏掉未找到的返回值：走完数组仍可能没有目标。使用 −1、None 或可选类型，让调用方区分未找到和下标 0。