数据结构与算法 / 系统课时
算法正确性说明
算法正确性说明
测试可以发现具体错误,却不能覆盖所有合法输入。正确性说明需要把输入前提、循环不变量、状态更新和终止条件连接起来。本课以下界二分查找为主示例,说明如何用“初始化、保持、终止”证明返回位置一定是第一个不小于目标值的下标。
学习目标
- 使用循环不变量描述每轮都成立的事实
- 分别说明不变量的初始化、保持与终止结论
- 使用严格减小的循环度量证明算法一定结束
建立下界二分的不变量
输入数组必须按非递减顺序排列。算法返回最小下标 i,使 a[i] >= target;若不存在这样的元素,则返回 a.length。只有先写清这两个条件,后续证明才知道哪些事实可以使用、最终需要推出什么结论。
下界二分使用半开搜索区间 [left, right)。可以把答案理解为“小于目标值的区域”和“不小于目标值的区域”之间的分界点。
每轮循环开始时保持三个事实:[0, left) 中的元素都小于目标值;[right, length) 中的元素都不小于目标值;真实答案始终位于闭区间 [left, right]。
初始化时 left = 0、right = length,左右两个已确认区域都为空,因此不变量成立。若 a[middle] < target,则借助数组有序性可排除 [left, middle],更新 left = middle + 1;否则 middle 仍可能是答案,应更新 right = middle。两种分支都不会排除真实分界点。

主示例:下界二分查找
下面的 Java 17 程序查找目标值 7 的下界,并额外验证目标值超过全部元素时返回数组长度。
public class BinarySearchCorrectnessDemo {
private record Result(int index, int iterations) {
}
public static void main(String[] args) {
int[] sorted = {1, 3, 5, 7, 9, 11};
Result found = lowerBound(sorted, 7);
Result missing = lowerBound(sorted, 12);
System.out.println("目标 7 的下界: " + found.index());
System.out.println("对应元素: " + sorted[found.index()]);
System.out.println("循环次数: " + found.iterations());
System.out.println("目标 12 的下界: " + missing.index());
}
private static Result lowerBound(int[] values, int target) {
int left = 0;
int right = values.length;
int iterations = 0;
while (left < right) {
iterations++;
int middle = left + (right - left) / 2;
// 保留第一个可能满足 values[i] >= target 的位置。
if (values[middle] < target) {
left = middle + 1;
} else {
right = middle;
}
}
return new Result(left, iterations);
}
}将代码保存为 BinarySearchCorrectnessDemo.java,然后编译运行:
javac BinarySearchCorrectnessDemo.java
java BinarySearchCorrectnessDemo预期输出:
目标 7 的下界: 3
对应元素: 7
循环次数: 3
目标 12 的下界: 6说明终止性与常见误区
循环度量可以选 right - left。它始终是非负整数,并且每轮至少缩小 1,因此循环不可能无限执行。结束时 left == right,未确定区间为空;结合不变量,左侧都小于目标值,当前位置及其右侧都不小于目标值,所以该位置正是下界。
执行一个样例只能展示一条轨迹,不能代替一般证明。另一个常见问题是证明使用半开区间,而代码却按闭区间更新,导致不变量与实现脱节。正确性说明必须与实际初始化、循环条件和边界更新逐句对应。