数据结构与算法 / 系统课时
算法测试与边界用例
算法测试与边界用例
算法在一个典型输入上得到正确结果,只能说明这条路径可用。本课以二分查找为主例,建立接口契约,覆盖正常、边界、异常与规模场景,并把失败用例保留为回归测试。
学习目标
- 能根据算法契约设计正常、边界和异常用例。
- 能使用自动化断言验证返回值、输入状态和重复值行为。
- 能通过失败测试复现缺陷并形成回归用例。
先明确算法契约
测试之前应先说明什么输入合法、什么结果算正确。本课约定二分查找接收升序整数序列;命中时返回任意一个合法匹配下标,未命中返回 -1;函数不修改输入,也不主动检查序列是否有序。
契约决定断言方式。例如序列含有重复值时,测试不应强制要求固定下标,而应验证返回位置合法且对应元素等于目标值。无序输入不属于本接口的合法测试数据,除非实现明确承诺检查并抛出异常。

用例应覆盖哪些路径
高价值测试不是简单增加数量,而是覆盖不同控制流。二分查找至少应检查空序列、单元素命中与未命中、首尾元素、目标小于最小值、目标大于最大值、重复值以及较大输入。
断言也要覆盖完整行为:返回下标必须合法,命中位置的值必须等于目标,未命中必须返回 -1,调用前后的输入序列必须一致。发现缺陷后,应先写出稳定失败的测试,再修复实现并永久保留该用例。
主示例:用 unittest 验证二分查找
下面的单文件示例包含算法实现和测试入口,可直接保存为 test_binary_search.py。辅助断言统一验证返回值和输入未被修改,重复值测试则按“任意合法匹配位置”的契约判断。
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()运行命令:
python test_binary_search.py预期输出:
..........
----------------------------------------------------------------------
Ran 10 tests in <TIME>s
OK<TIME> 会随机器性能变化。若把循环条件误改为 left < right,单元素命中或尾部命中等测试会失败,因为左右边界重合时最后一个候选位置没有被检查。
常见误区与改进
只测试“目标位于中间”无法覆盖边界更新和循环终止条件;只判断结果不等于 -1,也无法证明返回位置正确。测试应围绕外部契约,而不是绑定变量名、循环次数或具体实现方式。
规模测试可以发现死循环、明显退化和数据规模相关缺陷,但不能代替复杂度分析。性能测试也不宜使用极短且固定的耗时阈值,否则容易受机器负载影响而产生偶发失败。