02.03 搜索与循环不变量：在有序消息序号中定位补拉起点
02.03 搜索与循环不变量：在有序消息序号中定位补拉起点
DeepTutor 原稿经技术和教学审阅后的章节。数据、程序和结果均为静态教学模型；本次没有运行 Go、测试、站点构建或 OpenIM。
本章从哪里开始
02.02 把消息计划任务排成线性次序。现在考虑另一项虚构 IM 需求：会话 c-a 的本地历史以整数键排序，学习者已看过键 5，想找到第一条键严格大于 5 的本地记录。若切片为 [1,3,5,8,13]，起点是下标 3、键值 8。
这个问题先要分清四种名字：
| 名字 | 回答什么 | 能否直接相互替代 |
|---|---|---|
| 消息 ID | 哪条业务消息 | 不能由下标或正文推出 |
| 排序键 | 记录按什么比较 | 相等键未必是同一条消息 |
| 切片下标 | 当前本地数组的哪个位置 | 插删后可变化 |
lastSeen | 本题给出的上次已见键 | 尚不是实际服务端游标 |
本章只计算当前本地输入中的边界位置。它不发送补拉请求，不验证权限、历史保留、服务端序号、网络分页、消息送达或已读。示例中允许重复的整数排序键，只为讲清二分边界；不能据此宣称真实 IM 可重复使用同一唯一序号。
| 第一遍 | 第二遍 | 综合 |
|---|---|---|
| 顺序扫描、位置与存在性 | 半开区间、二分不变量、下界与上界 | sort.Search 和补拉决策表 |
先修是 01.01–01.05、02.01–02.02：函数、循环、切片、结构体、线性次序、操作成本与不变量直觉。02.05 才会系统讲排序算法；本章把“输入已按同一键非降序排列”写成调用前提。
一、没有排序前提，先逐项扫描
无论切片是否排序，都能从下标 0 起逐项检查“是否大于 lastSeen”：
func firstGreaterLinear(seqs []int64, lastSeen int64) int {
for i, seq := range seqs {
if seq > lastSeen {
return i
}
}
return len(seqs)
}返回 i 表示它是当前切片顺序中第一个满足条件的位置；返回 n=len(seqs) 表示没有满足项。n 是合法的“末尾边界”或未命中标记，却不是可读取下标；调用者必须先检查 i<n 再访问 seqs[i]。空切片的 n=0，自然返回 0。
例如无序切片 [1,8,3,6] 且 lastSeen=5，扫描首先在下标 1 找到 8。这不意味着 seqs[1:] 全部大于 5，因为后面仍有 3。若需求是“找出所有更大的记录”，无序输入要逐项筛选，不能只取一个后缀。
扫描不变量在每次检查下标 i 之前成立：所有 j<i 都已检查且 seqs[j]≤lastSeen。初始 i=0 时此前无元素，命题成立；若当前不满足，把它纳入已检查前缀，下一轮仍成立；若当前满足，因为前缀都不满足，它就是首次命中；若遍历结束，全部元素都不满足，返回 n 正确。
固定宽整数的比较按本章成本模型为 O(1)，扫描最坏要比较 n 项，时间 O(n)、额外空间 O(1)。如果比较的是可变长度正文，单次比较的字节成本还应另外计算。
二、排序让“首次满足”形成边界
现在额外要求序列非降序：每一项不大于下一项，允许相等。教学数组为：
下标 i | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
a[i] | 1 | 3 | 3 | 6 | 8 | 11 |
对目标 3，谓词 a[i]≥3 沿下标变成 假、真、真、真、真、真；谓词 a[i]>3 则是 假、假、假、真、真、真。这种先假后真的单调形态，才允许一次比较排除一整段位置。数组 [1,8,3,6] 对 >5 得到“假、真、假、真”，不能这样排除。
我们用 [lo,hi) 表示尚未分类的数组下标：包括 lo，不包括 hi。初始为 [0,n)；长度是 hi-lo；lo==hi 时没有未分类元素。下标 n 不属于数组，却可以是“应插在末尾”的答案边界。
要特别区分两句话：未分类的元素位置在 [lo,hi)；最终的分界位置可以等于 hi，所以答案始终在闭区间 [lo,hi] 中。原始生成稿把这两种范围混在一起，若答案为 n 就无法解释；本章以下始终分别使用。
三、二分下界：第一个不小于目标的位置
定义 lowerBound(a,target) 为最小下标 i，使 a[i]≥target；若没有这样的元素，返回 n。它不是“找到恰好等于目标”，而是返回一个边界。
func lowerBound(a []int64, target int64) int {
lo, hi := 0, len(a)
for lo < hi {
mid := lo + (hi-lo)/2
if a[mid] < target {
lo = mid + 1
} else {
hi = mid
}
}
return lo
}mid := lo+(hi-lo)/2 先求宽度再加回 lo，避免直接相加 lo+hi 的潜在整数溢出；lo<hi 保证 mid 是有效未分类下标。
循环每次开始时维持：
0≤lo≤hi≤n。- 对所有
i<lo，有a[i]<target：左侧已经确定不满足。 - 对所有
i≥hi且i<n，有a[i]≥target：右侧已经确定满足。
初始化 lo=0,hi=n，两侧已分类区间都为空，不变量成立。若 a[mid]<target，排序保证 mid 及其左侧都更小，故令 lo=mid+1；若 a[mid]≥target，mid 可能是最左满足位置，不能丢掉它，令 hi=mid。两种更新都不排除真正的分界位置。
以 target=3 逐轮核对：
| 轮次 | [lo,hi) | mid | a[mid] | 更新后 |
|---|---|---|---|---|
| 1 | [0,6) | 3 | 6 | hi=3，得 [0,3) |
| 2 | [0,3) | 1 | 3 | hi=1，得 [0,1) |
| 3 | [0,1) | 0 | 1 | lo=1，得 [1,1) |
结束时 lo==hi==1。不变量说明 1 左侧全小于 3，1 及右侧全不小于 3，所以 1 是下界。空输入直接返回 0；目标小于首项返回 0；目标大于末项返回 n。每轮未分类区间长度严格缩小，因此循环终止。这份初始化、保持、终止与结果解释，才是对一类有序输入的证明；手算三轮只是帮助看清它。
四、上界与重复值：严格大于目标
定义 upperBound(a,target) 为第一个 a[i]>target 的位置。只需把谓词换为严格大于：
func upperBound(a []int64, target int64) int {
lo, hi := 0, len(a)
for lo < hi {
mid := lo + (hi-lo)/2
if a[mid] <= target {
lo = mid + 1
} else {
hi = mid
}
}
return lo
}这次左侧已分类部分满足 a[i]≤target，右侧满足 a[i]>target。对数组 [1,3,3,6,8,11]：
| 目标 | 下界 ≥ | 上界 > | 解释 |
|---|---|---|---|
| 0 | 0 | 0 | 小于首项 |
| 1 | 0 | 1 | 1 只在下标 0 |
| 3 | 1 | 3 | 两个 3 占等值段 [1,3) |
| 4 | 3 | 3 | 不存在 4；两个边界都在下标 3 |
| 11 | 5 | 6 | 11 是末项；没有更大项 |
| 12 | 6 | 6 | 超过末项，返回 n |
对 target=3 再逐轮核对上界，可与第三节的下界表比较：
| 轮次 | [lo,hi) | mid | a[mid] | 更新后 |
|---|---|---|---|---|
| 1 | [0,6) | 3 | 6 | hi=3，得 [0,3) |
| 2 | [0,3) | 1 | 3 | lo=2，得 [2,3) |
| 3 | [2,3) | 2 | 3 | lo=3，得 [3,3) |
下界在见到等于 3 的中点时向左保留，上界则把等于 3 的中点也归入左侧已分类区。差别只有一个等号，返回值却从 1 变为 3。用重复键测试这两个函数，比只用互不相等的输入更能暴露符号写错。
若要按数值精确查找 4，不能因为 lowerBound 返回下标 3 就说找到了 4。应先检查 i<len(a)，再检查 a[i]==4；下标 3 的值是 6，所以未找到。对 target=12，先检查长度更重要，直接访问 a[6] 会越界。
重复值也暴露补拉语义风险：若 lastSeen=3，upperBound(3) 会跳过所有等于 3 的记录。如果真实系统允许不同消息拥有相同排序键，客户端只看过其中一条，就不能仅凭整数 3 安全跳过其余记录；需要稳定复合游标，或按明确协议重拉等值段后去重。这里允许重复只是算法教学，不代表真实消息序号可以重复。
例如当前排序键和消息身份分别为 (3,m-a)、(3,m-b)、(6,m-c)。客户端只处理过 m-a，却把 lastSeen=3 交给严格上界，结果直接从 m-c 开始，m-b 被跳过。若协议选择复合游标 (seq,messageID)，就必须先定义二者的整体比较顺序，再按该整体键排序与搜索；若协议选择只用整数键，则要明确同键记录全部确认后才能推进游标。算法不会自动替业务补上这项约定。
五、用 sort.Search 表达“首个为真”
Go 标准库 sort.Search(n,f) 返回 [0,n) 中第一个让 f(i) 为真的下标；若没有，返回 n。它依赖调用者保证谓词按下标呈“先假后真”，不会替你验证输入是否有序。
下面是独立完整程序。firstGreater 对已排序切片实现本地“严格晚于 lastSeen”的起点；sort.Search 中的匿名函数读取外层 seqs、lastSeen，是 01.03 已学过的函数值与闭包用法。
package main
import (
"fmt"
"sort"
)
func firstGreater(seqs []int64, lastSeen int64) int {
return sort.Search(len(seqs), func(i int) bool {
return seqs[i] > lastSeen
})
}
func main() {
seqs := []int64{1, 3, 3, 6, 8, 11}
for _, lastSeen := range []int64{0, 1, 3, 4, 11, 12} {
start := firstGreater(seqs, lastSeen)
if start == len(seqs) {
fmt.Println(lastSeen, "本地没有更大的键")
continue
}
fmt.Println(lastSeen, "从下标", start, "键值", seqs[start], "开始")
}
}按上表预期 lastSeen=3 得下标 3、值 6；lastSeen=11 或 12 得 n=6，不能再访问 seqs[6]。空切片时 sort.Search(0,f) 返回 0，不调用 f。这只是本地数组位置结论。
六、复杂度与失败前提
二分每轮把未分类下标区间缩到约一半；对长度 n 的随机访问切片和固定宽整数比较，比较次数为 O(log(n+1))，额外空间 O(1)。线性扫描最坏比较 n 项，为 O(n)。若每次谓词要读取长正文、访问链表中点或执行网络请求，单次判断不再是本章的 O(1) 操作，整体成本也不能照搬。
把 n 从 8 增到 16、32、64，二分最多只需要增加约 1、2、3 轮，因为每轮继续把未分类区间折半；线性扫描最坏则可能多检查 8、24、56 项。这是比较次数模型，并未测出纳秒时间。若数据尚未排序，先检查非降序要 O(n)；若每次临时排序，成本还包含排序；只有长期维护有序数据或本来就按该键提供结果时，反复二分才可能获得期望的查找收益。
区间缩小不等于算法必然正确。无序数组 [1,8,3,6]，lastSeen=5，谓词是“假、真、假、真”。若第一次二分查看中点下标 2 的值 3，并据此排除左半边，就漏掉下标 1 的 8。它也会终止，却给出错误的“首次满足位置”。正确性需要输入非降序与谓词单调；若调用方必须先检查排序，逐项检查本身是 O(n)，这项成本要计入整个操作。
“当前数组的首个更大键”与“应有历史完整”也不同。对 [1,3,5]、lastSeen=2，算法正确返回键 3；它无法判断键 2、4 是合法过滤、保留期之外、从未存在，还是数据丢失。会话身份、权限、服务端游标、重试与去重属于后续同步协议；本章不把某个键差称为丢消息证据。
还要注意调用边界：若 seqs 包含多个会话的键，即使数字整体非降序，返回的位置也未必属于目标会话；若目标会话权限在客户端记录 lastSeen 后改变，旧位置也未必有可见数据。排序正确是二分所需的算法前提，但业务补拉还需要会话归属、授权和可见范围等独立前提。测试应分别记录哪一层已验证，不能用一个“二分测试通过”覆盖所有层。
七、业务决策：是下界、上界，还是精确查找
需求若说“至少从 5 开始重新检查”，应找 lowerBound(5)；若说“已经确认了键 5 的全部记录，只要更晚的”，应找 upperBound(5)。若说“消息 ID 为 m-a 的记录是否存在”，则应按 ID 精确查询，不能把一个数值插入点当消息身份。接口名称最好把比较符号写清，例如 firstSeqGreaterThan 比 findStart 更不容易误解。
在服务端补拉真实场景中，还要定义：lastSeen 是不是已确认的稳定游标？同键记录是否可能有多个？权限变化后，旧游标是否仍可用？空结果表示本次页为空、已经追平，还是还要继续翻页？这些条件未定义时，算法只能回答当前切片问题，不能替协议决定起点的全部语义。
阅读固定版本的 OpenIM 消息同步入口时，可带着问题查证它使用什么游标和边界。本章没有审计其实现，也不依据文件名推断实际同步规则。
八、分层练习：先写区间，再算答案
以下练习统一使用教学有序键 [1,3,3,6,8,11]，除非题目另给输入。先写 lo、hi、目标比较符号，再核对反馈。
1. 空数组求下界 5，返回什么？
返回 0，也是 n；没有可读取的下标 0。
2. 目标 0 的下界和上界？
都为 0，首项 1 已满足两种比较。
3. 目标 3 的下界？
1，指向第一个 3；相等时不能排除中点。
4. 目标 3 的上界？
3，指向 6；两个等于 3 的键占 [1,3)。
5. 目标 4 的两个边界都是 3，是否找到键 4？
没有。边界是插入位置；a[3] 为 6，精确查找还要比较值。
6. 目标 12 的下界与上界？
都为 6，即 n；不能访问 a[6]。
7. `[lo,hi)` 中哪个端点不包含？
hi 不包含；数组尚未分类的下标数量是 hi-lo。
8. 答案边界可能等于 `hi` 吗？
可以，尤其全部元素都小于目标时答案是 n。答案在 [lo,hi]，未分类元素在 [lo,hi)。
9. 下界里 `a[mid]<target` 时如何更新？
lo=mid+1；排序保证中点及左侧都不满足。
10. 下界里 `a[mid]>=target` 时为何令 `hi=mid`？
中点可能就是最左满足位置，不能直接排除它。
11. 为什么 `lo=mid` 可能无法结束？
当区间只剩两项且 mid==lo 时，lo 不前进；应在排除中点的分支设为 mid+1。
12. `mid` 的安全计算式？
lo+(hi-lo)/2，避免直接求 lo+hi 的潜在溢出。
13. 无序 `[1,8,3,6]` 对 `>5` 能否直接二分？
不能。谓词为假、真、假、真，不单调；下标 1 的 8 可能被错误排除。
14. 对未排序数组，线性扫描返回下标 1 后能取整个后缀吗？
不能。后缀中还可能有不满足的 3；若需要所有满足项，要继续逐项筛选。
15. `sort.Search` 返回 `n` 表示服务端没有更晚消息吗？
不表示。它只说明本次本地输入中没有使谓词为真的位置。
16. `lastSeen=3` 却只确认看过第一个 3，能直接用上界跳过两个 3 吗？
不能。若同键记录可共存，需要稳定复合游标或按协议重拉等值段并去重。
17. 二分 O(log n) 的前提？
切片可随机访问、输入按同一键排序、谓词单调，且单次比较按本模型为 O(1)。
18. 验证输入已排序需要怎样的成本？
逐项检查相邻项需 O(n) 次比较；要计入整次调用，不可只报告二分本身。
19. 下界返回的下标是否就是消息 ID？
不是。它是当前切片位置；消息身份必须由稳定字段表达。
20. `lastSeen=2`、数组 `[1,3,5]`，能由间隔断定丢消息吗？
不能。可能是过滤或保留规则，也可能缺数据；算法只定位当前数组的首个更大键。
来源与下一步
- Go
sort.Search核对“首个使单调谓词为真”的标准库合同。 - Algorithms, 4th Edition：基础模型与MIT 6.006 笔记目录用于核对查找与成本模型；本章的 IM 例子是原创教学设定。
下一章02.04 哈希与集合从有序边界转向按复合消息 ID 的精确查找与本地去重；本章的二分只负责当前有序序列中的边界位置。