数据结构与算法 / 系统课时
排查算法错误与异常
排查算法错误与异常
算法故障常只在某个边界输入上出现,大量日志反而会掩盖关键状态。本课将用一个二分查找错误演示完整排查路径:稳定复现、缩小用例、检查不变量、最小修复和回归验证。
学习目标
- 保存足够信息,使随机或偶发失败可以稳定重放
- 将大型输入缩小为最小失败用例
- 根据关键状态和循环不变量定位根因
先让故障稳定复现
排查前应记录完整输入、程序版本、配置、随机种子、期望结果、实际结果和异常堆栈。随机测试若没有保存种子,下一次运行可能无法重现同一问题。
复现后再逐步删除元素、缩小数值范围或减少操作序列。每次修改只要故障仍存在,就保留更小的输入,直到无关状态被去除。最小用例通常能直接暴露错误分支。

用不变量检查关键状态
调试日志应放在影响决策的位置,例如 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修复后的验证范围
修复应尽量小,一次只改动一个有证据支持的位置。随后增加永久回归测试,至少覆盖空数组、单元素、首部命中、尾部命中和未命中,防止同类边界错误再次出现。
大型算法还可使用随机对拍:同一输入分别交给待测实现和一个简单可信的参考实现,结果不一致时保存种子与输入。若修复改变了执行路径,还应重新做性能测试,确认正确性修复没有引入不可接受的退化。
按自己的节奏,确认真正理解。