第4卷第2章积跬步，致千里

从顺序查找的逐行调试出发，精确推导找到与未找到时的运行步数，再用指示器统一分支，并以哨兵算法比较常数优化、计算模型与渐近分析。

学习目标

能用逐行调试记录顺序查找的控制流，并从首次命中位置 M 推导找到与未找到两种运行步数
能明确每行等成本的计算模型，用成功指示器 S 把两个分支统一为 4M−3S+5
能把目标写入 A[n+1] 构造哨兵，推导 3M−3S+7 并量化何时比普通版更快
能用交互实验比较精确步数、常数优化和 O(n) 渐近结论，识别可写空间与恢复成本等工程前提

从“一眼就能看见26”开始

新学年开始了。泰朵拉带来村木老师的算法卡片，也带来一位红发、抱着红色笔记本电脑、说话极简的新生：双仓理纱。她是双仓博士的女儿，敲键盘又快又安静。第1章还在讨论不确定的选择，第2章却故意选了一个答案一目了然的问题：

A=\{31,41,59,26,53\}, \qquad v=26.

人能直接看见26，计算机却只能依照给定步骤，从第一个元素开始检查。原章的挑战不在“能不能找到”，而在三个更严格的问题：

算法究竟运行了哪些步骤？
输入改变后，运行步数怎样用公式表示？
一个看似微小的改写，能否被定量证明更快？

先预测：普通顺序查找在第M个位置首次找到目标时，为什么不是只用M步？若完全找不到，循环体执行n次，循环条件又执行多少次？加入哨兵后，算法会从线性时间变成常数时间吗？

2.1 高中

2.1.1 泰朵拉

泰朵拉决定学习。她先总结算法的五项特征：输入、输出、确定性、可行性与有穷性。

“步骤明确”不等于“看起来合理”。要验证它，最直接的办法是把自己想成计算机：只看当前行、当前变量和当前跳转，不提前利用人眼已经知道的答案。这种笨拙的执行方式正是理解算法的第一步。

2.1.2 理纱

理纱很少加入对话，却在大家完成一次逐行调试后指出真正值得记录的量：按行计算运行次数。具体输入得到18步只是一个测试用例；目标可能在开头、末尾、重复出现，也可能根本不在数列中，规模n还可能达到一百万。

她把问题从“这次跑了几步”提升为“所有允许输入分别要跑几步”。这个转变把程序演示变成了算法分析。

2.1.3 顺序查找

的输入与输出是：

输入数列 $A=\{A[1],A[2],\ldots,A[n]\}$ ；
输入数列大小n；
输入目标值 $v$ ；
若某个元素等于 $v$ ，输出“能找到”；
否则输出“无法找到”。

用伪代码写成：

procedure LINEAR-SEARCH(A, n, v)
L2: k <- 1
L3: while k <= n do
L4:   if A[k] = v then
L5:     return "能找到"
L6:   end-if
L7:   k <- k + 1
L8: end-while
L9: return "无法找到"
L10: end-procedure

这里的把语言语法细节拿走，却保留了赋值、条件、循环、返回与控制流。算法不是一句“从头找”，而是一条从输入走到输出的可执行道路。

2.1.4 逐行调试

对A={31,41,59,26,53}、n=5、v=26执行：

令k=1，检查边界，再比较31与26；
不相等，令k=2，比较41与26；
再自增，比较59与26；
当k=4时，A[4]=26，立即返回“能找到”；
返回后不再执行自增、循环出口和失败返回。

若把过程入口、每一行与过程结束都按原章规则计作一步，总共是18步。的价值不是替代真实运行，而是暴露“我以为会执行”和“实际上会执行”的差别。

2.1.5 顺序查找算法分析

先要规定怎样计量。本章采用一个简化但实用的：每行伪代码的运行时间相同。因此，求运行时间可以转化为求各行运行次数之和。

这不是说真实机器上的赋值和数组比较永远同速，而是说比较必须建立在共同前提上。若没有成本模型，“算法更快”只是一句无法验证的印象。

控制流成本必须算进去；找不到时 while 条件要执行 n+1 次。

2.1.6 顺序查找算法分析：能找到 $v$

设v第一次出现的位置是M。若数列里有多个v，顺序查找会在最小位置停下，所以M不是任意一个出现位置，而是首次出现位置。

各行次数为：

行	含义	次数
L1	进入过程	$1$
L2	初始化`k`	$1$
L3	检查 $k\le n$	$M$
L4	比较 $A[k]=v$	$M$
L5	成功返回	$1$
L6	结束条件块	$0$
L7	`k`自增	$M-1$
L8	回到循环	$M-1$
L9	失败返回	$0$
L10	结束过程	$1$

所以：

\begin{aligned} T_{\mathrm{found}}(M) &=1+1+M+M+1+0+(M-1)+(M-1)+0+1\\ &=4M+2. \end{aligned}

代入测试用例M=4：

T_{\mathrm{found}}(4)=4\cdot4+2=18,

与逐行调试完全一致。用具体例子回代，是发现公式漏项的最低成本检验。

目标位置 M=4 只描述命中位置；18步还包括控制流和返回。

2.1.7 顺序查找算法分析：无法找到 $v$

找不到时，所有n个元素都要比较。关键是循环条件运行n+1次：

k=1,2,\ldots,n

时要判断为真，执行完第n次循环后，还要在k=n+1时再判断一次为假，算法才能跳到失败返回。因此L3运行n+1次，不是n次。

各行次数为：

1,\ 1,\ n+1,\ n,\ 0,\ 0,\ n,\ n,\ 1,\ 1.

总步数：

\begin{aligned} T_{\mathrm{miss}}(n) &=1+1+(n+1)+n+0+0+n+n+1+1\\ &=4n+5. \end{aligned}

2.2 算法分析

2.2.1 米尔嘉

米尔嘉加入后，没有满足于两个独立公式。她先补齐前提：运行步数只有在每一步成本已定义时才能代表速度；随后追问能否把“找到”和“找不到”归纳为一种情况。

她的方法不是抹掉差异，而是给差异命名。只要新增变量具有清晰定义、不会产生矛盾，就可以把多个分支放入同一个式子中研究。

2.2.2 明确计算模型

算法分析至少包含四步：

明确允许的输入与算法输出；
规定基本操作及其成本，也就是计算模型；
对不同输入统计资源消耗；
用公式比较、验算并解释结果。

本章按行等成本，因此公式保留了常数项。它能回答“这个测试到底18步还是16步”“哨兵从第几个位置开始占优”等精细问题。后面的渐近分析会忽略部分细节，回答规模增长的共同趋势。

2.2.3 不同情况的归纳

定义：找到时S=1，找不到时S=0。

S= \begin{cases} 1,&\text{在A中能找到v},\\ 0,&\text{在A中无法找到v}. \end{cases}

再定义：

M= \begin{cases} \min\{k:A[k]=v\},&S=1,\\ n,&S=0. \end{cases}

于是S指示成功，1-S指示失败；重复v取最小位置。各行可统一写为：

行	统一次数	当 $S=1$	当 $S=0,\ M=n$
L1	$1$	$1$	$1$
L2	$1$	$1$	$1$
L3	$M+1-S$	$M$	$n+1$
L4	$M$	$M$	$n$
L5	$S$	$1$	$0$
L6	$0$	$0$	$0$
L7	$M-S$	$M-1$	$n$
L8	$M-S$	$M-1$	$n$
L9	$1-S$	$0$	$1$
L10	$1$	$1$	$1$

求和：

\begin{aligned} T_{\mathrm{linear}}(M,S) &=1+1+(M+1-S)+M+S\\ &\quad+0+(M-S)+(M-S)+(1-S)+1\\ &=4M-3S+5. \end{aligned}

代回两种取值，验算两端：

S=1\Longrightarrow4M-3+5=4M+2,

S=0,\ M=n\Longrightarrow4n+5.

2.2.4 思考意义

统一公式真正有价值的地方，不只是少写一行。每个代数组合都应有可解释的意义：

S是“能找到v”的指示器；
1-S是“无法找到v”的指示器；
M-S是成功时的M-1次自增，或失败时的n次自增；
M+1-S是普通算法的while检查次数；
当成功时，M+1-S=M，正是目标首次出现的位置；
当失败时，M+1-S=n+1，那是原数组边界之外的第一个位置。

米尔嘉由最后一点提出关键改写：既然失败时目标不在A[1]至A[n]，就把v主动放进A[n+1]。这样无论原数组是否包含目标，M+1-S都能被看作搜索终止的位置。两种代数形态由一个真实的数据位置统一起来，这就是哨兵的入口。

2.2.5 带有哨兵的顺序查找算法

是写入A[n+1]的目标值：

procedure SENTINEL-LINEAR-SEARCH(A, n, v)
S2: A[n + 1] <- v
S3: k <- 1
S4: while A[k] != v do
S5:   k <- k + 1
S6: end-while
S7: if k <= n then
S8:   return "能找到"
S9: end-if
S10: return "无法找到"
S11: end-procedure

普通版每轮同时关心“越界了吗”和“命中了吗”。哨兵保证最迟在n+1处命中，所以循环内部只比较元素；退出后再用一次k\le n区分命中的是原数据还是哨兵。

仍沿用S与M，逐行次数为：

1,\ 1,\ 1,\ M+1-S,\ M-S,\ M-S,\ 1,\ S,\ 0,\ 1-S,\ 1.

因此：

\begin{aligned} T_{\mathrm{sentinel}}(M,S) &=1+1+1+(M+1-S)+(M-S)+(M-S)\\ &\quad+1+S+0+(1-S)+1\\ &=3M-3S+7. \end{aligned}

对原测试M=4,S=1：

T_{\mathrm{sentinel}}(4,1)=12-3+7=16,

测试用例16步，比普通版18步少2步。一般地：

\begin{aligned} T_{\mathrm{linear}}-T_{\mathrm{sentinel}} &=(4M-3S+5)-(3M-3S+7)\\ &=M-2. \end{aligned}

所以当M\gt2时，哨兵版更快；M=2时相同；M=1时，为安放哨兵付出的固定成本反而使它多一步。找不到是最坏情况：普通版最坏4n+5，哨兵版最坏3n+7。

T_{\mathrm{linear,max}}=4n+5, \qquad T_{\mathrm{sentinel,max}}=3n+7.

当M很大时，主项从4M降为3M，哨兵版约为普通版的3/4，也就是主项操作约减少25%。但这种优化有工程前提：数组必须有可写的n+1位置；若不能破坏输入，还要保存并恢复原值，额外成本也应写进模型。

哨兵减少循环内的边界检查，但仍需在退出后区分原数组命中与哨兵命中。

2.2.6 创造历史

精确公式让“似乎更快”变成可复查的结论，这就是明确前提条件的定量评估：任何人都能看到前提、重复计算、提出改良。泰朵拉把这种可继承的定量评估想成“创造历史”——思想不依赖作者本人留在现场，也能被未来的人验证和使用。

同时，米尔嘉提醒不要把显微镜只对准常数差异。对大规模问题，把两种顺序查找都归为：

T(n)\in O(n).

这里的O(n)没有否定哨兵约25%的主项改进。精确分析回答同一模型下“差多少、何时占优”，渐近分析回答“规模增大时属于哪种增长类型”。原章在理纱说出尚未真正理解的O(n)处停住，为后文保留进一步解释。

高德纳在20世纪60年代创造“算法分析”这一名字。这个名字强调的不只是写出程序，而是用可共享的数学语言研究算法本身。

2.3 自己家：笨拙的一步

夜里，“我”重新整理当天的收获：算法从输入出发，依靠明确、可行的操作，在有限步内得到输出；逐行调试看似笨拙，却能把控制流真正变成自己的理解；数学公式则让评估、比较和判断有了共同尺度。

泰朵拉有踏实执行的毅力，米尔嘉善于追问变量的意义，理纱迅速看见哨兵。面对三个人各自的长处，“我”一度自惭形秽，又想起自己正处于高三。高考这一比特也像一次沉重的测试用例：合格是1，不合格是0，那是关系人生道路的一比特指示器。

这并不意味着人生能被一个公式概括。它把本章的算法语言带回现实：一次评价可以输出一比特，但真正能控制的是今晚是否展开笔记本，继续踏出笨拙的一步。“积跬步，致千里”既描述顺序查找一个元素一个元素地前进，也描述学习者一次只把眼前一步做明确。

泰朵拉的伪代码笔记

章后笔记把本章用到的控制结构整理成可执行语义：

procedure定义带参数的流程，end-procedure结束流程；
赋值把右侧表达式的值写入左侧变量，交换赋值则互换两个变量；
if只在条件为真时执行分支，if/else保证两个分支恰有一个执行；
多个else-if按顺序测试，命中后跳过其余分支；
while先检查条件，真则执行循环体并回到条件，假则跳出；
return立即结束流程：它给出输出，并转到过程结束处，不继续执行后续语句。

这些规则解释了为什么成功返回后L7至L9不再执行，也解释了为什么while必须多做一次失败测试。伪代码可以不属于某门编程语言，但控制流不能含糊。

官方概念回收：把控制流变成证据

官方概念锚点补全：一个算法必须明确且无歧义，并在有限步后停止；本章的输入数列大小n、目标值和返回结果都公开。逐行调试记录程序位置、变量与分支，原测试用例的第18步就是核对公式的锚点。首次命中时，M不是任意一个出现位置，而是重复v取最小位置；4乘4加2等于18。

未找到时，所有n个元素都要比较，循环条件运行n+1次，循环终止必须被观察到。统一分支就是把找到和找不到归纳为一种情况：成功指示器S在找到时S=1、找不到时S=0，1-S指示失败，找不到时约定M=n。哨兵把目标主动放进A[n+1]，退出后再用一次k小于等于n区分原数据命中与末端哨兵命中。

精确比较表明 M大于2时哨兵版更快；普通版最坏4n+5，哨兵版最坏3n+7，主项从4M降为3M，但数组必须有可写的n+1位置。两种顺序查找都是O(n)，所以常数优化没有改变增长阶；算法分析这一名字强调的是公开模型、逐行统计和可复查的数学语言。伪代码语义也不能省略：while先检查条件，return立即结束流程。

分步1 / 4

1. 执行：沿着数组逐项前进

记录每一行、每次比较和每次分支，不让人眼提前跳到目标；M=4 的样例应得到18步。

目标位置 M=4 只描述命中位置；18步还包括控制流和返回。

本章回顾：把每一步变成可解释的数量

顺序查找从A[1]开始，首次命中目标或检查完A[n]后停止。
算法具有输入、输出、确定性、可行性和有穷性。
逐行调试记录程序位置、变量和分支，不允许人眼提前跳到答案。
本章采用每行等成本的简化计算模型。
对测试A={31,41,59,26,53}、v=26，普通版运行18步。
若首次命中位置为M，普通版运行4M+2步。
若找不到目标，while条件运行n+1次，总步数是4n+5。
成功指示器S在找到时为1，找不到时为0。
找到时M是目标首次出现位置，找不到时约定M=n。
普通版两种情况统一为4M-3S+5。
1-S指示失败，M+1-S统一了循环检查次数。
在A[n+1]写入v形成哨兵，保证搜索不会越过该位置。
哨兵版把循环内的边界检查移到退出后，总步数为3M-3S+7。
普通版减哨兵版等于M-2，所以在本模型中M\gt2时哨兵占优。
最坏情况下，普通版为4n+5，哨兵版为3n+7。
大规模时主项比例约为3/4，可解释为约25%的主项操作减少。
两种算法仍都是O(n)；精确计数与渐近分析回答不同问题。
定量结论必须公开计算模型、输入假设与额外写入成本。
伪代码的if、while与return都具有严格控制流语义。
笨拙的一步既是算法执行方式，也是持续学习的方法。

交互实验

搜索步数：常数优化到底省了多少

输入规模

n=10

首次命中

M=4

当前步数

普通版：`4M−3S+5=18`；哨兵版：`3M−3S+7=16`。当 M 大于2时，哨兵版在这个逐行模型中更快，但两者仍都是线性搜索。

练习与答案

练习

问题 1：找到与未找到。 对 M=4 的成功样例，为什么普通顺序查找是 4M+2=18 步？若找不到，为什么 while 条件是 n+1 次？

问题 2：统一公式。 令 S=1 表示找到、S=0 表示找不到，并约定失败时 M=n。验证 4M−3S+5 能同时还原两种公式。

问题 3：哨兵改进。 为什么将 v 写入 A[n+1] 后能减少主项，却不能把复杂度从线性变成常数？

问题 4：计算模型。 为什么“每行等成本”不是机器真实时间，却仍然是有用的算法分析起点？

名词解释

本章出现的专业名词，用大白话再讲一遍。

算法: 从输入出发，经明确、可行且有限步骤产生输出的过程。
顺序查找: 从数组第一个元素起逐项比较，直到命中或检查完全部元素的算法。
逐行调试: 按程序位置、变量和分支逐行模拟算法执行的验证方法。
计算模型: 规定基本操作成本以便比较运行资源的假设。
成功指示器S: 找到目标时取1、找不到时取0的分支编码。
哨兵: 预先把目标写入数组末端，使循环无需每次检查边界的值。

正式目录节点：逐项释义

下面补齐本章正文已经涉及、但容易被公式或叙事压缩掉的节点。每一项都给出对象、验证动作与边界；它们是第4卷第2章积跬步，致千里的知识证据，不是把目录标题重复一遍。

确定性：“确定性”在第4卷第2章积跬步，致千里中承担一个可检查的概念节点：先说明它所描述的对象与问题，再沿本章的推导或实验观察一次结果，最后用边界或反例复核适用范围；这段解释把术语和可复现的判断步骤绑定起来，而不是只保留名称。
可行性：“可行性”在第4卷第2章积跬步，致千里中承担一个可检查的概念节点：先说明它所描述的对象与问题，再沿本章的推导或实验观察一次结果，最后用边界或反例复核适用范围；这段解释把术语和可复现的判断步骤绑定起来，而不是只保留名称。
有穷性：“有穷性”在第4卷第2章积跬步，致千里中承担一个可检查的概念节点：先说明它所描述的对象与问题，再沿本章的推导或实验观察一次结果，最后用边界或反例复核适用范围；这段解释把术语和可复现的判断步骤绑定起来，而不是只保留名称。
A=53：“A=53”在第4卷第2章积跬步，致千里中是一个可回代的记号或中间结论：先写清变量、定义域与前提，再按本章给出的公式或程序执行一步，最后把结果代回原约束检查；只记住符号外形而不检查边界，不能算作完成理解。
v=26：“v=26”在第4卷第2章积跬步，致千里中是一个可回代的记号或中间结论：先写清变量、定义域与前提，再按本章给出的公式或程序执行一步，最后把结果代回原约束检查；只记住符号外形而不检查边界，不能算作完成理解。
无法找到：“无法找到”在第4卷第2章积跬步，致千里中承担一个可检查的概念节点：先说明它所描述的对象与问题，再沿本章的推导或实验观察一次结果，最后用边界或反例复核适用范围；这段解释把术语和可复现的判断步骤绑定起来，而不是只保留名称。
用具体例子回代：“用具体例子回代”在第4卷第2章积跬步，致千里中承担一个可检查的概念节点：先说明它所描述的对象与问题，再沿本章的推导或实验观察一次结果，最后用边界或反例复核适用范围；这段解释把术语和可复现的判断步骤绑定起来，而不是只保留名称。
无法找到v：“无法找到v”在第4卷第2章积跬步，致千里中承担一个可检查的概念节点：先说明它所描述的对象与问题，再沿本章的推导或实验观察一次结果，最后用边界或反例复核适用范围；这段解释把术语和可复现的判断步骤绑定起来，而不是只保留名称。
M-S：“M-S”在第4卷第2章积跬步，致千里中是一个可回代的记号或中间结论：先写清变量、定义域与前提，再按本章给出的公式或程序执行一步，最后把结果代回原约束检查；只记住符号外形而不检查边界，不能算作完成理解。
4M-3S+5：“4M-3S+5”在第4卷第2章积跬步，致千里中是一个可回代的记号或中间结论：先写清变量、定义域与前提，再按本章给出的公式或程序执行一步，最后把结果代回原约束检查；只记住符号外形而不检查边界，不能算作完成理解。
代回两种取值：“代回两种取值”在第4卷第2章积跬步，致千里中承担一个可检查的概念节点：先说明它所描述的对象与问题，再沿本章的推导或实验观察一次结果，最后用边界或反例复核适用范围；这段解释把术语和可复现的判断步骤绑定起来，而不是只保留名称。
保证搜索不会越过该位置：“保证搜索不会越过该位置”是第4卷第2章积跬步，致千里中的正式知识节点：本章不把它当作标题或口号，而是给出对象、操作和成立条件，再用一个具体例子完成计算或推理，并说明改变一个前提时哪一步会失效；这样才能把概念迁移到新的题目。
带有哨兵的顺序查找算法：“带有哨兵的顺序查找算法”是第4卷第2章积跬步，致千里中的正式知识节点：本章不把它当作标题或口号，而是给出对象、操作和成立条件，再用一个具体例子完成计算或推理，并说明改变一个前提时哪一步会失效；这样才能把概念迁移到新的题目。
3M-3S+7：“3M-3S+7”在第4卷第2章积跬步，致千里中是一个可回代的记号或中间结论：先写清变量、定义域与前提，再按本章给出的公式或程序执行一步，最后把结果代回原约束检查；只记住符号外形而不检查边界，不能算作完成理解。
测试用例16步：“测试用例16步”在第4卷第2章积跬步，致千里中是一个可回代的记号或中间结论：先写清变量、定义域与前提，再按本章给出的公式或程序执行一步，最后把结果代回原约束检查；只记住符号外形而不检查边界，不能算作完成理解。
普通版18步少2步：“普通版18步少2步”在第4卷第2章积跬步，致千里中是一个可回代的记号或中间结论：先写清变量、定义域与前提，再按本章给出的公式或程序执行一步，最后把结果代回原约束检查；只记住符号外形而不检查边界，不能算作完成理解。
M-2：“M-2”在第4卷第2章积跬步，致千里中是一个可回代的记号或中间结论：先写清变量、定义域与前提，再按本章给出的公式或程序执行一步，最后把结果代回原约束检查；只记住符号外形而不检查边界，不能算作完成理解。
精确计数与渐近分析回答不同问题：“精确计数与渐近分析回答不同问题”是第4卷第2章积跬步，致千里中的正式知识节点：本章不把它当作标题或口号，而是给出对象、操作和成立条件，再用一个具体例子完成计算或推理，并说明改变一个前提时哪一步会失效；这样才能把概念迁移到新的题目。
自己家：“自己家”是第4卷第2章积跬步，致千里中的叙事锚点：它把人物、问题和当时可用的观察条件固定下来；阅读到这里时，应先记录场景限制，再把后续公式或算法放回同一条件下复核，避免把故事转成脱离上下文的结论。
procedure：“procedure”在第4卷第2章积跬步，致千里中是一个可回代的记号或中间结论：先写清变量、定义域与前提，再按本章给出的公式或程序执行一步，最后把结果代回原约束检查；只记住符号外形而不检查边界，不能算作完成理解。
if/else：“if/else”在第4卷第2章积跬步，致千里中是一个可回代的记号或中间结论：先写清变量、定义域与前提，再按本章给出的公式或程序执行一步，最后把结果代回原约束检查；只记住符号外形而不检查边界，不能算作完成理解。