数据结构与算法 / 系统课时

算法正确性说明

算法正确性说明

测试可以发现具体错误,却不能覆盖所有合法输入。正确性说明需要把输入前提、循环不变量、状态更新和终止条件连接起来。本课以下界二分查找为主示例,说明如何用“初始化、保持、终止”证明返回位置一定是第一个不小于目标值的下标。

学习目标

  • 使用循环不变量描述每轮都成立的事实
  • 分别说明不变量的初始化、保持与终止结论
  • 使用严格减小的循环度量证明算法一定结束

建立下界二分的不变量

输入数组必须按非递减顺序排列。算法返回最小下标 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 的下界,并额外验证目标值超过全部元素时返回数组长度。

java
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,然后编译运行:

bash
javac BinarySearchCorrectnessDemo.java
java BinarySearchCorrectnessDemo

预期输出:

text
目标 7 的下界: 3
对应元素: 7
循环次数: 3
目标 12 的下界: 6

说明终止性与常见误区

循环度量可以选 right - left。它始终是非负整数,并且每轮至少缩小 1,因此循环不可能无限执行。结束时 left == right,未确定区间为空;结合不变量,左侧都小于目标值,当前位置及其右侧都不小于目标值,所以该位置正是下界。

执行一个样例只能展示一条轨迹,不能代替一般证明。另一个常见问题是证明使用半开区间,而代码却按闭区间更新,导致不变量与实现脱节。正确性说明必须与实际初始化、循环条件和边界更新逐句对应。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

算法正确性说明

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通