边界条件与调试方法

4.1 边界条件与调试方法

本节摘要：算法想清楚了，输往往输在执行上。本节整理高频边界清单，给出"暴力对拍、中间状态打印、二分定位"的系统化调试流程，并交代白板场景下的代码自检顺序——这套方法论从考场一直通到生产排障。

为什么本地全过、一提交就挂

前三章解决了"怎样变快"，最后一章解决"怎样变稳、怎样讲清"。先把最疼的问题摆上桌：很多人的解法逻辑完全正确，样例也过，提交却在第几十个用例上失败。原因几乎总是边界——算法正文处理的是"一般情形"，而评测用例专挑"特殊情形"。更隐蔽的是，这类失败还伴随时间黑洞：无头苍蝇式地改代码、重提交，半小时就没了。本节的目标是把"处理边界"和"定位错误"都变成清单动作，不靠灵感靠流程。

一、高频边界清单

按数据形态整理，做题收尾时过一遍：

两个最经典的案例值得展开。其一，整数溢出：求两数平均值的写法 (lo 加 hi) 整除 2，当 lo 与 hi 都接近整数上限时相加即溢出，正确写法是 lo 加 (hi 减 lo) 整除 2——差值不会溢出。这个 bug 在真实的标准库实现里都存在过，足见其隐蔽。其二，二分查找的边界：lo 小于等于 hi 还是小于、hi 等于 mid 还是 mid 减一，四种组合对应不同的区间约定，混用必错。自查口诀是"区间是闭是开，死循环当心中点不前进"。

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1          # 闭区间约定
    while lo <= hi:                    # 闭区间要允许 lo 等于 hi
        mid = lo + (hi - lo) // 2      # 防溢出写法
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1               # mid 已查过，必须跳过
        else:
            hi = mid - 1
    return -1

print(binary_search([1, 3, 5, 7, 9], 7))    # 输出 3
print(binary_search([7], 7))                # 输出 0，单元素
print(binary_search([], 7))                 # 输出 -1，空输入
​

二、系统化调试：缩小不确定域

对拍是算法题最有力的调试武器：写个朴素但必然正确的暴力解，再用随机数据生成器批量造输入，两个实现的输出一有分歧立刻打印现场。它的价值在于把"我的优化版哪里错了"这个大问题压缩成"分歧输入长什么样"这个小问题。流程如下：

import random

def max_subarray_brute(nums):          # 平方级暴力，作为对照组
    best = nums[0] if nums else 0
    n = len(nums)
    for i in range(n):
        s = 0
        for j in range(i, n):
            s += nums[j]
            best = max(best, s)
    return best

def max_subarray_fast(nums):           # 线性贪心，待验证版本
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

for _ in range(10000):
    nums = [random.randint(-10, 10) for _ in range(random.randint(1, 12))]
    if max_subarray_brute(nums) != max_subarray_fast(nums):
        print("分歧输入：", nums)
        break
# 若两版本不一致，分歧输入会立刻暴露，再对它打印中间状态定位
​

定位阶段的二分思想同样适用：如果怀疑错误发生在某个中间步骤，打印中间状态时不要全量打印，先看一半位置的状态对不对——对则错在后半，错则错在前半，几轮就把出错点夹出来。这套"对拍锁答案、二分锁位置"的组合拳，迁移到工程排障就是日志埋点加二分回滚版本，方法论完全同构。

三、白板与面试的自检节奏

面试手写代码没有编译器，自检顺序要固定成肌肉记忆：第一遍过边界——空输入、单元素、极值各在心里跑一遍；第二遍过循环——首尾两轮迭代手动模拟，变量更新顺序有没有颠倒；第三遍过返回——所有分支都有返回值、返回类型与签名一致。写之前先花几句话复述思路并报出复杂度，写的过程中主动说"这里我用闭区间约定"，写完主动补"我再过一遍空输入和单元素"——这些话本身就是强信号，面试官听到就知道你有工程纪律。调试方法论的本节版本可以浓缩成一句话：不要猜，要缩小不确定域；清单管住边界，对拍管住正确性，二分管住定位。

四、一个完整案例：从翻车到定位

看个真实感很强的翻车案例。目标函数是"移除有序数组中的重复项，返回新长度"，初学者常见写法用快慢指针，但边界条件写成"快指针从零开始"，于是首个元素被当成"与前一个比较"而误删或误留；另一常见版本是慢指针先加一再赋值，首元素处理顺序错位，单元素数组返回零。两个 bug 都不会在任何双元素以上的规整用例上暴露，唯独单元素与空输入一击即中——这正是边界清单里"空输入、单元素"两行存在的意义。

def remove_duplicates(nums):
    if not nums:                 # 空输入前置判断，缺了就崩
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1              # 长度是下标加一，单元素返回一

print(remove_duplicates([1, 1, 2]))       # 输出 2
print(remove_duplicates([5]))             # 输出 1
print(remove_duplicates([]))              # 输出 0
​

定位这类问题的过程值得复盘：现象是"部分用例通过、特定长度失败"。第一步查边界清单，空与单元素各跑一遍，立刻发现单元素返回错误；第二步检查首尾迭代，手动模拟 fast 从一到末尾的每轮，发现慢指针初值与循环起点配合有误；第三步修正后用对拍脚本跑上万组随机输入兜底。整个过程几分钟内完成，靠的是流程而非灵感。把这个节奏练熟，面试现场写错的代价就从"手忙脚乱改到超时"降为"有章法地两分钟修复"，后者在面试官眼里同样是加分表现——工程纪律的展示机会，有时就藏在写错的那一刻。

本节要点回顾

• 翻车主因是边界不是算法：空、单元素、全同、有序、极值、负数六类用例收尾必查；
• 防溢出写法：中点用 lo 加差值折半，真实标准库都栽过；
• 二分四组合：区间开闭与 mid 跳过方式要配套，混用即错；
• 对拍是终极武器：随机数据加暴力对照，分歧输入一出现错误现场就锁定；
• 自检三遍过：过边界、过首尾迭代、过返回分支，顺序固定成习惯。

下一节空间复杂度优化：时间账算完之后，空间账怎么继续省——原地操作、滚动变量与状态压缩三板斧。