线性搜索从第一项开始查看列表，直到找到目标或没有项可查。考试中通常会给你算法和一些数据，要求你完成追踪表并说出结果。
本课属于搜索、排序与文件，用到重复结构与数组中的循环和数组概念。
如何一步步追踪算法？
追踪表为每个变量设一列，每当数值变化就新增一行。你要扮演计算机：读一行代码，只更新这一行改变的内容，并写下新的数值。
三个习惯让追踪更可靠：
- 列出代码中出现的每个变量，包括
Found这样的标志变量。 - 每次都先判断循环条件，再进入循环体。
- 把没变的值抄到下一行，让每一行都显示完整状态。
例题
一家虚构商店把六个产品代码存在数组里，位置为 1 到 6。
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Codes | 14 | 9 | 27 | 9 | 31 | 5 |
Found ← FALSE
Index ← 1
WHILE Index <= 6 AND Found = FALSE
IF Codes[Index] = Target THEN
Found ← TRUE
ELSE
Index ← Index + 1
ENDIF
ENDWHILE
IF Found = TRUE THEN
OUTPUT "Found at position ", Index
ELSE
OUTPUT "Not found"
ENDIFTarget = 27 时的追踪。
| 步骤 | Index | Codes[Index] | Codes[Index] = Target？ | Found |
|---|---|---|---|---|
| 开始 | 1 | FALSE | ||
| 第 1 轮 | 1 | 14 | 否 | FALSE |
| 第 2 轮 | 2 | 9 | 否 | FALSE |
| 第 3 轮 | 3 | 27 | 是 | TRUE |
第 3 轮之后 Found 为 TRUE，条件不成立，循环结束。输出是 Found at position 3，共比较三次。
Target = 8 时的追踪。 没有任何代码等于 8，所以循环在 Index = 1、2、3、4、5、6 时各比较一次，六次都不匹配。第六次之后 Index 变成 7，条件 Index <= 6 不成立，循环结束，Found 仍是 FALSE。输出是 Not found，搜索共比较六次。
要留意的错误
下面这个版本在匹配之后仍然移动下标：
WHILE Index <= 6 AND Found = FALSE
IF Codes[Index] = Target THEN
Found ← TRUE
ENDIF
Index ← Index + 1
ENDWHILETarget = 27 时，匹配发生在 Index = 3，可是加一的那行仍会执行，所以循环结束前 Index 变成 4。输出会说位置 4，而 Codes[4] 是 9，不是 27。
改正方法是把 Index ← Index + 1 放进 ELSE 分支，让它只在没有匹配时才执行。追踪时，每一行都问自己：“哪一行改变了这个变量？它有资格执行吗？”
自我检测
使用同样的数组和算法。
1. Target = 31。输出是什么？比较了几次？
显示答案
Index 依次为 1、2、3、4、5。Codes[5] = 31 在第五次比较时匹配。输出：Found at position 5，比较五次。
2. Target = 9。报告哪个位置？为什么位置 4 永远不会被报告？
显示答案
Codes[2] = 9 在第二次比较时匹配，Found 变为 TRUE，循环结束。输出：Found at position 2。位置 4 也是 9，但循环在到达它之前就停止了。
3. Target = 5。比较了几次？对于存在的目标，这是最好还是最坏的情况？
显示答案
5 排在最后，位置 6，所以比较六次。这是目标存在时的最坏情况，因为每一项都被检查了。
接下来学什么
追踪熟练之后，试试解释一轮排序，那里的数值会移动，而不只是被读取。受限伪代码追踪训练器可以逐步运行这样的算法，让你把自己的表和机器的结果对照。
有些学生能读懂代码，却因为追踪表悄悄漏掉一次变化而丢分。这正是我们的老师在一对一线上计算机科学补习中会留意的习惯。