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

数值与边界错误排查

数值与边界错误排查

算法公式正确并不代表程序实现安全。整数溢出、浮点比较、非法下标、空集合和过深递归都可能在极端输入下触发错误。本课将这些问题统一为可检查的边界条件,并给出确定性的修复与验证方法。

学习目标

  • 识别整数溢出、浮点误差、数组越界和空输入的典型症状。
  • 在计算前扩大数值类型,并为索引、集合和递归深度建立显式约束。
  • 通过边界用例验证修复结果,而不是只依赖正常输入。

故障类型与检查重点

故障类型 常见表现 安全做法
整数溢出 结果变负数、排序比较异常、距离突然变小 运算前转换为 long,避免结果产生后再转换
浮点误差 0.1 + 0.2 == 0.3 为 false 使用绝对误差与相对误差结合的近似比较
数组越界 首尾位置偶发崩溃 明确合法区间是 [0, length)
空输入 访问首元素或除以元素个数时失败 在方法入口定义空输入语义
递归过深 大数据下出现 StackOverflowError 改用显式栈或迭代,并设置深度保护

边界排查应从输入契约开始。先确定空数组、负数、最大值和重复值是否允许,再检查实现是否与契约一致。没有明确契约时,调用方和实现方往往会对同一输入做出不同假设。

定位顺序

  1. 使用最小失败用例复现问题,并记录触发值、下标和输入长度。
  2. 检查表达式中间结果的类型。即使最终变量是 long,两个 int 相乘仍会先按 int 计算。
  3. 对所有下标写出合法区间,重点检查 length - 1、循环终点和二分中点。
  4. 为长度为 0、长度为 1、最大值、最小值和接近阈值的输入建立测试。
  5. 对递归算法估算最坏深度;深度可能接近输入规模时,优先改为迭代实现。

完整可运行示例

下面的 Java 17 程序集中演示安全求和、安全中点、浮点近似比较、数组下标校验、空输入校验和迭代替代深递归。

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

bash
javac NumericBoundaryDemo.java
java NumericBoundaryDemo

预期输出

text
安全求和: 4294967294
安全中点: 2050000000
浮点原始结果: 0.30000000000000004
近似相等: true
最大值: 9
越界检查: index=3, length=3
空输入检查: values must not be empty
迭代倒计时步数: 5

safeSum 从累加开始就使用 long,因此不会先发生 int 溢出。safeMidpoint 使用 left + (right - left) / 2,避免直接计算 left + right。浮点比较同时考虑绝对差和数值尺度,比固定比较 == 更可靠。

修复与验证

修复整数溢出时,错误写法是先完成窄类型运算再转换,例如 (long) (a * b);正确做法是让至少一个操作数先成为 long,例如 (long) a * b。二分查找、图最短路和计数累加都应检查中间结果,而不只检查返回类型。

数组循环应明确采用哪一种边界:遍历元素通常使用 index < length,访问相邻元素时还要保证 index + 1 < length。空输入不能由偶然异常定义行为,应选择返回空结果、返回默认值或主动抛出带明确信息的异常。

递归问题不能只用较小样例验证。对于链式树、退化图或单调输入,应构造最坏深度测试;若深度可能与 nn 同阶,使用显式栈或迭代通常比单纯增大线程栈更可控。

本课总结

  • 数值安全取决于中间表达式的类型,而不只是最终变量的类型。
  • 下标、空输入和递归深度都应成为显式契约,并由边界用例验证。
  • 修复后必须覆盖最小值、最大值、空集合、首尾下标和最坏结构。

下一课预告

下一阶段将进入综合验收与工程化实践,把正确性测试、性能指标、边界用例和回归检查组合成可重复执行的算法质量保障流程。

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

目录与阅读设置

阅读设置

17

记录一个想法

数值与边界错误排查

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

登录哪都通