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

算法测试与边界用例

算法测试与边界用例

算法在一个典型输入上得到正确结果,只能说明这条路径可用。本课以二分查找为主例,建立接口契约,覆盖正常、边界、异常与规模场景,并把失败用例保留为回归测试。

学习目标

  • 能根据算法契约设计正常、边界和异常用例。
  • 能使用自动化断言验证返回值、输入状态和重复值行为。
  • 能通过失败测试复现缺陷并形成回归用例。

先明确算法契约

测试之前应先说明什么输入合法、什么结果算正确。本课约定二分查找接收升序整数序列;命中时返回任意一个合法匹配下标,未命中返回 -1;函数不修改输入,也不主动检查序列是否有序。

契约决定断言方式。例如序列含有重复值时,测试不应强制要求固定下标,而应验证返回位置合法且对应元素等于目标值。无序输入不属于本接口的合法测试数据,除非实现明确承诺检查并抛出异常。

二分查找测试设计矩阵

用例应覆盖哪些路径

高价值测试不是简单增加数量,而是覆盖不同控制流。二分查找至少应检查空序列、单元素命中与未命中、首尾元素、目标小于最小值、目标大于最大值、重复值以及较大输入。

断言也要覆盖完整行为:返回下标必须合法,命中位置的值必须等于目标,未命中必须返回 -1,调用前后的输入序列必须一致。发现缺陷后,应先写出稳定失败的测试,再修复实现并永久保留该用例。

主示例:用 unittest 验证二分查找

下面的单文件示例包含算法实现和测试入口,可直接保存为 test_binary_search.py。辅助断言统一验证返回值和输入未被修改,重复值测试则按“任意合法匹配位置”的契约判断。

python
import unittest
from collections.abc import Sequence

def binary_search(values: Sequence[int], target: int) -> int:
    left = 0
    right = len(values) - 1

    while left <= right:
        middle = left + (right - left) // 2
        value = values[middle]

        if value == target:
            return middle
        if value < target:
            left = middle + 1
        else:
            right = middle - 1

    return -1

class BinarySearchTest(unittest.TestCase):
    def assert_search(
        self,
        values: list[int],
        target: int,
        expected: int,
    ) -> None:
        original = values.copy()
        actual = binary_search(values, target)

        self.assertEqual(expected, actual)
        self.assertEqual(original, values)

        if actual != -1:
            self.assertEqual(target, values[actual])

    def test_empty(self) -> None:
        self.assert_search([], 3, -1)

    def test_single_match(self) -> None:
        self.assert_search([3], 3, 0)

    def test_single_missing(self) -> None:
        self.assert_search([3], 2, -1)

    def test_first(self) -> None:
        self.assert_search([1, 3, 5, 7, 9], 1, 0)

    def test_last(self) -> None:
        self.assert_search([1, 3, 5, 7, 9], 9, 4)

    def test_missing_between(self) -> None:
        self.assert_search([1, 3, 5, 7, 9], 4, -1)

    def test_outside_range(self) -> None:
        self.assert_search([1, 3, 5, 7, 9], 10, -1)

    def test_negative_values(self) -> None:
        self.assert_search([-10, -5, -2, 0, 8], -2, 2)

    def test_duplicates(self) -> None:
        values = [1, 3, 3, 3, 5]
        original = values.copy()
        index = binary_search(values, 3)

        self.assertIn(index, {1, 2, 3})
        self.assertEqual(3, values[index])
        self.assertEqual(original, values)

    def test_large_input(self) -> None:
        values = list(range(100_000))
        self.assert_search(values, 99_999, 99_999)

if __name__ == "__main__":
    unittest.main()

运行命令:

bash
python test_binary_search.py

预期输出:

text
..........
----------------------------------------------------------------------
Ran 10 tests in <TIME>s

OK

<TIME> 会随机器性能变化。若把循环条件误改为 left < right,单元素命中或尾部命中等测试会失败,因为左右边界重合时最后一个候选位置没有被检查。

常见误区与改进

只测试“目标位于中间”无法覆盖边界更新和循环终止条件;只判断结果不等于 -1,也无法证明返回位置正确。测试应围绕外部契约,而不是绑定变量名、循环次数或具体实现方式。

规模测试可以发现死循环、明显退化和数据规模相关缺陷,但不能代替复杂度分析。性能测试也不宜使用极短且固定的耗时阈值,否则容易受机器负载影响而产生偶发失败。

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

目录与阅读设置

阅读设置

17

记录一个想法

算法测试与边界用例

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

登录哪都通