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

用小样例手动走完整算法

用小样例手动走完整算法

代码写得快并不代表边界一定正确。编码前先挑一个足够小、但能触发关键分支的样例,把指针、状态和判断条件逐轮写出来,可以在几分钟内暴露循环边界、更新顺序和终止条件的问题。

学习目标

  • 选择能覆盖关键分支的最小样例
  • 用状态表逐轮验证循环边界与更新顺序
  • 把手动推演结果与实际程序输出进行对照

先选能暴露错误的小样例

手动模拟不是随便找一组输入。样例应当足够小,让你能完整走完算法,同时至少触发一次状态更新和一次关键判断。以二分查找 [1, 3, 5, 7] 中的 5 为例,两轮循环就能检查中点计算、左右边界更新和命中后的终止行为。

如果只拿目标恰好位于第一次中点的位置测试,很多错误分支根本不会执行。更稳妥的做法是先问自己:这个样例能不能迫使算法至少走一次我最担心的分支?

把每一轮状态写出来

假设采用闭区间 [left, right],初始状态为 left = 0、right = 3。每轮只记录会影响下一轮的状态:

轮次 left right mid nums[mid] 动作
1 0 3 1 3 3 < 5,令 left = mid + 1
2 2 3 2 5 命中,立即结束

这张表能直接检查三个问题:循环条件是否允许检查最后一个元素;排除 mid 后是否使用 mid + 1 或 mid - 1;命中后是否真的停止。若你的代码状态变化与表格不同,就应该先修正模板,而不是继续补更多测试数据。

用程序复现手动过程

下面把每轮状态打印出来,让程序执行轨迹与手工表格一一对应。

python
def binary_search(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2
        print(f'left={left}, right={right}, mid={mid}, value={nums[mid]}')

        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1


nums = [1, 3, 5, 7]
index = binary_search(nums, 5)
print(f'index={index}')

预期输出

text
left=0, right=3, mid=1, value=3
left=2, right=3, mid=2, value=5
index=2

输出与手动状态表一致,说明这条执行路径上的边界、更新顺序和终止条件彼此匹配。实际面试中不需要把整张表写得很正式,只要在纸上或脑中维护关键状态即可。

优先推演最危险的地方

不同算法需要观察的状态不同。双指针重点看两个指针是否可能越界或错过答案;滑动窗口重点看扩张、统计、收缩的先后顺序;动态规划重点看当前状态依赖的数据是否已经计算完成;DFS 和回溯则要确认选择、递归与撤销操作是否成对出现。

当一个样例无法覆盖这些关键动作时,再补第二个针对性样例,而不是一开始就手算很大的输入。编码前的手动推演目标不是证明算法对所有输入都正确,而是尽早发现模板中的结构性错误。

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

目录与阅读设置

阅读设置

17

记录一个想法

用小样例手动走完整算法

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

登录哪都通