数据结构与算法 / 系统课时
数值与边界错误排查
数值与边界错误排查
算法公式正确并不代表程序实现安全。整数溢出、浮点比较、非法下标、空集合和过深递归都可能在极端输入下触发错误。本课将这些问题统一为可检查的边界条件,并给出确定性的修复与验证方法。
学习目标
- 识别整数溢出、浮点误差、数组越界和空输入的典型症状。
- 在计算前扩大数值类型,并为索引、集合和递归深度建立显式约束。
- 通过边界用例验证修复结果,而不是只依赖正常输入。
故障类型与检查重点
| 故障类型 | 常见表现 | 安全做法 |
|---|---|---|
| 整数溢出 | 结果变负数、排序比较异常、距离突然变小 | 运算前转换为 long,避免结果产生后再转换 |
| 浮点误差 | 0.1 + 0.2 == 0.3 为 false |
使用绝对误差与相对误差结合的近似比较 |
| 数组越界 | 首尾位置偶发崩溃 | 明确合法区间是 [0, length) |
| 空输入 | 访问首元素或除以元素个数时失败 | 在方法入口定义空输入语义 |
| 递归过深 | 大数据下出现 StackOverflowError |
改用显式栈或迭代,并设置深度保护 |
边界排查应从输入契约开始。先确定空数组、负数、最大值和重复值是否允许,再检查实现是否与契约一致。没有明确契约时,调用方和实现方往往会对同一输入做出不同假设。
定位顺序
- 使用最小失败用例复现问题,并记录触发值、下标和输入长度。
- 检查表达式中间结果的类型。即使最终变量是
long,两个int相乘仍会先按int计算。 - 对所有下标写出合法区间,重点检查
length - 1、循环终点和二分中点。 - 为长度为 0、长度为 1、最大值、最小值和接近阈值的输入建立测试。
- 对递归算法估算最坏深度;深度可能接近输入规模时,优先改为迭代实现。
完整可运行示例
下面的 Java 17 程序集中演示安全求和、安全中点、浮点近似比较、数组下标校验、空输入校验和迭代替代深递归。
public class NumericBoundaryDemo {
public static void main(String[] args) {
int[] largeValues = {Integer.MAX_VALUE, Integer.MAX_VALUE};
System.out.println("安全求和: " + safeSum(largeValues));
int left = 2_000_000_000;
int right = 2_100_000_000;
System.out.println("安全中点: " + safeMidpoint(left, right));
double actual = 0.1 + 0.2;
System.out.println("浮点原始结果: " + actual);
System.out.println("近似相等: " + nearlyEqual(actual, 0.3, 1e-12));
int[] values = {4, 9, 2};
System.out.println("最大值: " + max(values));
try {
System.out.println(valueAt(values, 3));
} catch (IndexOutOfBoundsException exception) {
System.out.println("越界检查: " + exception.getMessage());
}
try {
System.out.println(max(new int[0]));
} catch (IllegalArgumentException exception) {
System.out.println("空输入检查: " + exception.getMessage());
}
System.out.println("迭代倒计时步数: " + countDownIteratively(5));
}
private static long safeSum(int[] values) {
long total = 0L;
for (int value : values) {
total += value;
}
return total;
}
private static int safeMidpoint(int left, int right) {
if (left > right) {
throw new IllegalArgumentException("left must not exceed right");
}
return left + (right - left) / 2;
}
private static boolean nearlyEqual(double left, double right, double epsilon) {
double difference = Math.abs(left - right);
double scale = Math.max(1.0, Math.max(Math.abs(left), Math.abs(right)));
return difference <= epsilon * scale;
}
private static int valueAt(int[] values, int index) {
if (index < 0 || index >= values.length) {
throw new IndexOutOfBoundsException(
"index=" + index + ", length=" + values.length);
}
return values[index];
}
private static int max(int[] values) {
if (values.length == 0) {
throw new IllegalArgumentException("values must not be empty");
}
int result = values[0];
for (int index = 1; index < values.length; index++) {
result = Math.max(result, values[index]);
}
return result;
}
private static int countDownIteratively(int start) {
if (start < 0) {
throw new IllegalArgumentException("start must be non-negative");
}
int steps = 0;
for (int current = start; current > 0; current--) {
steps++;
}
return steps;
}
}将代码保存为 NumericBoundaryDemo.java,然后运行:
javac NumericBoundaryDemo.java
java NumericBoundaryDemo预期输出
安全求和: 4294967294
安全中点: 2050000000
浮点原始结果: 0.30000000000000004
近似相等: true
最大值: 9
越界检查: index=3, length=3
空输入检查: values must not be empty
迭代倒计时步数: 5safeSum 从累加开始就使用 long,因此不会先发生 int 溢出。safeMidpoint 使用 left + (right - left) / 2,避免直接计算 left + right。浮点比较同时考虑绝对差和数值尺度,比固定比较 == 更可靠。
修复与验证
修复整数溢出时,错误写法是先完成窄类型运算再转换,例如 (long) (a * b);正确做法是让至少一个操作数先成为 long,例如 (long) a * b。二分查找、图最短路和计数累加都应检查中间结果,而不只检查返回类型。
数组循环应明确采用哪一种边界:遍历元素通常使用 index < length,访问相邻元素时还要保证 index + 1 < length。空输入不能由偶然异常定义行为,应选择返回空结果、返回默认值或主动抛出带明确信息的异常。
递归问题不能只用较小样例验证。对于链式树、退化图或单调输入,应构造最坏深度测试;若深度可能与 同阶,使用显式栈或迭代通常比单纯增大线程栈更可控。
本课总结
- 数值安全取决于中间表达式的类型,而不只是最终变量的类型。
- 下标、空输入和递归深度都应成为显式契约,并由边界用例验证。
- 修复后必须覆盖最小值、最大值、空集合、首尾下标和最坏结构。
下一课预告
下一阶段将进入综合验收与工程化实践,把正确性测试、性能指标、边界用例和回归检查组合成可重复执行的算法质量保障流程。