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

排查算法错误与异常

排查算法错误与异常

算法故障常只在某个边界输入上出现,大量日志反而会掩盖关键状态。本课将用一个二分查找错误演示完整排查路径:稳定复现、缩小用例、检查不变量、最小修复和回归验证。

学习目标

  • 保存足够信息,使随机或偶发失败可以稳定重放
  • 将大型输入缩小为最小失败用例
  • 根据关键状态和循环不变量定位根因

先让故障稳定复现

排查前应记录完整输入、程序版本、配置、随机种子、期望结果、实际结果和异常堆栈。随机测试若没有保存种子,下一次运行可能无法重现同一问题。

复现后再逐步删除元素、缩小数值范围或减少操作序列。每次修改只要故障仍存在,就保留更小的输入,直到无关状态被去除。最小用例通常能直接暴露错误分支。

二分查找边界错误状态图

用不变量检查关键状态

调试日志应放在影响决策的位置,例如 left、right、middle 的更新前后,而不是无控制地打印整个循环。闭区间二分查找维护的候选区间是 [left, right],只要 left <= right,区间中就仍可能存在答案。

若循环使用 left < right,当区间缩小到一个元素时会提前结束,最后一个候选位置没有被检查。这类错误不能只靠异常捕获解决,因为程序通常会返回一个看似合法的错误结果。

主示例

下面的 Java 17 程序保留一个故意错误的实现,并用最小失败用例 [1, 3] 查找 3。正确实现只修改循环边界,便于确认根因来自最后一个候选元素被跳过。

java
import java.util.Arrays;

public class AlgorithmDebuggingDemo {
    public static void main(String[] args) {
        int[] values = {1, 3};
        int target = 3;

        System.out.println("失败输入: " + Arrays.toString(values) + ", target=" + target);
        System.out.println("错误实现结果: " + buggy(values, target));
        System.out.println("正确实现结果: " + correct(values, target));
        System.out.println("根因: left == right 时仍需检查该位置");
        System.out.println("回归验证通过: " + regressionPassed());
    }

    // 故意保留错误条件,用于重现“最后一个候选未检查”的故障。
    private static int buggy(int[] values, int target) {
        int left = 0;
        int right = values.length - 1;

        while (left < right) {
            int middle = left + (right - left) / 2;
            if (values[middle] == target) {
                return middle;
            }
            if (values[middle] < target) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return -1;
    }

    // 闭区间 [left, right] 非空时,left <= right 必须继续检查。
    private static int correct(int[] values, int target) {
        int left = 0;
        int right = values.length - 1;

        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (values[middle] == target) {
                return middle;
            }
            if (values[middle] < target) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return -1;
    }

    // 回归用例覆盖空数组、单元素、首尾命中与未命中。
    private static boolean regressionPassed() {
        return correct(new int[0], 1) == -1
                && correct(new int[]{5}, 5) == 0
                && correct(new int[]{1, 3}, 1) == 0
                && correct(new int[]{1, 3}, 3) == 1
                && correct(new int[]{1, 3}, 2) == -1;
    }
}

将代码保存为 AlgorithmDebuggingDemo.java,再编译运行:

bash
javac AlgorithmDebuggingDemo.java
java AlgorithmDebuggingDemo

预期输出:

text
失败输入: [1, 3], target=3
错误实现结果: -1
正确实现结果: 1
根因: left == right 时仍需检查该位置
回归验证通过: true

修复后的验证范围

修复应尽量小,一次只改动一个有证据支持的位置。随后增加永久回归测试,至少覆盖空数组、单元素、首部命中、尾部命中和未命中,防止同类边界错误再次出现。

大型算法还可使用随机对拍:同一输入分别交给待测实现和一个简单可信的参考实现,结果不一致时保存种子与输入。若修复改变了执行路径,还应重新做性能测试,确认正确性修复没有引入不可接受的退化。

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

目录与阅读设置

阅读设置

17

记录一个想法

排查算法错误与异常

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

登录哪都通