01先把问题说具体
在无序数组 [7,2,7,4] 中找 7,要求返回第一次出现的下标;目标不存在时返回 −1。
02一步步得到方法
没有额外结构时,先做可靠的基线
从左向右逐个比较,找到就返回。不要求有序、不建立索引,也不改变输入。这个简单方法常是优化前的正确性参考:二分利用排序,哈希利用预处理,线性扫描则不依赖这些前提。
接口中的第一个很关键。若只需任意匹配,多个位置都可接受;若需所有位置,不能提前返回。算法输出约定决定控制流。
一次查询与很多次查询
单次扫描不必先排序。若同一份静态数据上要做大量查询,可先建哈希索引保存各值第一次出现的位置。预处理花 O(n) 时间和空间,再换取平均常数查询;不能把预处理成本藏起来。
最弱前提往往最通用
线性查找不需要排序、可哈希或随机访问。只要能依次读取元素并判断是否匹配,就可以运行;链表、流式输入和自定义判定都能使用同一思路。
提前返回让最好情况为常数时间,最坏仍需检查全部 n 项。如果要找全部匹配而非第一个,就不能在首次命中时停止,还要把输出规模计入成本。
03把一个小例子完全算清楚
[7,2,7,4] 中查找 4。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| i=0 | 7≠4 | 已排除前缀 [0,1) |
| i=1、2 | 2≠4、7≠4 | 前面均不匹配 |
| i=3 | 4=4,返回 3 | 这是第一个匹配 |
窄屏可左右滑动表格,阅读完整计算与理由。
循环之前的所有元素都已排除,所以遇到目标时可以立即返回。
04为什么这个方法成立
- 初始已检查前缀为空。
- 每次不匹配就将该位置加入失败前缀。
- 第一次命中前没有匹配;若循环结束仍未命中,目标不存在。
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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
查找 7 返回哪里?
需要一点提示
按左到右顺序。
查看解析与答案
返回 0,不是 2。
空数组查找返回什么?
需要一点提示
循环不会进入。
查看解析与答案
返回 −1。
查一万次值得每次都扫描吗?
需要一点提示
先比较索引构建和查询总成本。
查看解析与答案
可建值到首次下标的字典,处理重复值时只保留第一次;需接受额外 O(n) 空间与更新维护成本。