专题进阶 · 搜索与回溯推荐总顺序 · 第 34 / 148 课

明确返回第一个匹配位置的含义,并从失败前缀证明线性搜索。

先学会这些,再进入本课 数组
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 搜索与回溯

线性搜索Linear Search

逐个比较,最坏 O(n),不需要有序性。

建议 35 分钟 · 含手算、代码与三层练习

本课要建立的能力

明确返回第一个匹配位置的含义,并从失败前缀证明线性搜索。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

在无序数组 [7,2,7,4] 中找 7,要求返回第一次出现的下标;目标不存在时返回 −1。

02一步步得到方法

没有额外结构时,先做可靠的基线

从左向右逐个比较,找到就返回。不要求有序、不建立索引,也不改变输入。这个简单方法常是优化前的正确性参考:二分利用排序,哈希利用预处理,线性扫描则不依赖这些前提。

接口中的第一个很关键。若只需任意匹配,多个位置都可接受;若需所有位置,不能提前返回。算法输出约定决定控制流。

一次查询与很多次查询

单次扫描不必先排序。若同一份静态数据上要做大量查询,可先建哈希索引保存各值第一次出现的位置。预处理花 O(n) 时间和空间,再换取平均常数查询;不能把预处理成本藏起来。

最弱前提往往最通用

线性查找不需要排序、可哈希或随机访问。只要能依次读取元素并判断是否匹配,就可以运行;链表、流式输入和自定义判定都能使用同一思路。

提前返回让最好情况为常数时间,最坏仍需检查全部 n 项。如果要找全部匹配而非第一个,就不能在首次命中时停止,还要把输出规模计入成本。

03把一个小例子完全算清楚

[7,2,7,4] 中查找 4。

步骤计算与状态为什么这样做
i=07≠4已排除前缀 [0,1)
i=1、22≠4、7≠4前面均不匹配
i=34=4,返回 3这是第一个匹配

窄屏可左右滑动表格,阅读完整计算与理由。

循环之前的所有元素都已排除,所以遇到目标时可以立即返回。

04为什么这个方法成立

  1. 初始已检查前缀为空。
  2. 每次不匹配就将该位置加入失败前缀。
  3. 第一次命中前没有匹配;若循环结束仍未命中,目标不存在。

05把推导翻译成代码

Python · 可独立运行的教学实现

def linear_search(a, target):
    for i, value in enumerate(a):
        if value == target:
            return i
    return -1

逐个理解关键决定

return i
找到立即结束保证首次出现。
return -1
必须放在循环外,否则第一个元素失配就错误终止。

06时间、空间与实现范围

最好 Θ(1),最坏 Θ(n),辅助空间 O(1)。若比较长字符串,单次相等比较成本需另算。

均匀成功位置下平均比较 (n+1)/2 次;该结论依赖具体分布,不适用于所有查询。

07改变条件,检查哪里会出错

返回 0 表示没找到

下标 0 是合法命中位置,应使用明确哨兵 −1 或可选值。

把未命中和下标0混淆

不要用0同时表示首元素和失败;明确使用 −1、None 或其他不冲突的约定。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

查找 7 返回哪里?

需要一点提示

按左到右顺序。

查看解析与答案

返回 0,不是 2。

练习 2 · 边界与辨析

空数组查找返回什么?

需要一点提示

循环不会进入。

查看解析与答案

返回 −1。

练习 3 · 变式与迁移

查一万次值得每次都扫描吗?

需要一点提示

先比较索引构建和查询总成本。

查看解析与答案

可建值到首次下标的字典,处理重复值时只保留第一次;需接受额外 O(n) 空间与更新维护成本。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。