笔试真题复盘：这段二分查找代码错在哪，你能找出几处

图 1：本文封面，三处紫色编号对应正文要排查的三个缺陷。

先说明属性：这是一篇笔试真题复盘，题目出自本地历史面试资料（一道「指出程序中所有问题」的代码找错题），与任何公司的当前招聘无关。题面给出一段 C++ 代码：在升序数组里查找最后一个等于目标值的元素，存在返回下标，不存在返回 -1。代码能编译，随手试几个例子甚至能跑对——但问题不止一处。

int BinarySearchMax(const std::vector<int>& data, int target) {
    int left = 0;
    int right = data.size();            // ①
    while (left < right) {
        int mid = (left + right) / 2;   // ②
        if (data[mid] <= target)
            left = mid;
        else
            right = mid - 1;
    }
    if (data[right] == target)          // ③
        return right;
    return -1;
}

先暴露的错误：死循环。

看循环骨架：循环条件是 left < right，收缩动作是「left = mid 或 right = mid − 1」——左边界会停在 mid 上。这种骨架想正常终止，mid 必须向上取整。反证：当区间只剩两个元素（right = left + 1）时，向下取整得到 mid = left；如果此时 data[left] <= target，执行 left = mid = left，左右边界都没动，循环原地打转。

拿实际数据跑：数组 {1, 2, 2}、目标 2。轨迹是 left = 0 → 1 → 2，之后每轮 mid 都等于 2，left 永远停在 2、right 永远是 3。笔者实测这个输入：进程跑了两秒没有任何输出，只能强制结束。这是缺陷②，也是这道题最容易被试出来的错。

被死循环掩盖的错误：上界越界。

把 mid 改成向上取整再试 {2, 2, 2}、目标 2：不死循环了，left 一路涨到 3——可数组长度就是 3，合法下标只有 0~2，最后一句 data[right] 读的是 data[3]。用 AddressSanitizer 编译运行，直接报 heap-buffer-overflow（堆缓冲区越界读）。

根因是初始化那行 right = data.size()。这段代码的候选区间是闭区间 [left, right]，right 应该指向最后一个合法下标 n − 1；写成 n，等于把「不存在的那个位置」也算进了候选。死循环存在时它没机会发作，修掉死循环它立刻咬人。这是缺陷①。

最安静的错误：空数组。

传入空数组会怎样？right = 0，循环条件一开始就不成立，循环体一次都不执行，直接走到 data[right]——读 data[0]。空数组根本没有第 0 个元素，实测 AddressSanitizer 报 SEGV（段错误）。这是缺陷③：入口少了判空。

图 2：三处缺陷的位置、根因与修法一一对应。

正确的写法不是背的，是推出来的。

先立不变量：答案（如果存在）始终落在闭区间 [left, right] 里。三条修复全是不变量的推论——right 必须初始化为 n − 1，否则区间混进了不存在的下标；收缩时「不可能含答案的一侧」排除 mid（right = mid − 1），「可能含答案的一侧」保留 mid（left = mid），而保留方向一旦是左边界，mid 就必须向上取整，否则左边界不前进；进循环前先处理空数组，否则不变量无从谈起。修完：

int BinarySearchMax(const std::vector<int>& data, int target) {
    if (data.empty()) return -1;                 // 修③：入口判空
    int left = 0, right = (int)data.size() - 1;  // 修①：最后一个合法下标
    while (left < right) {
        int mid = (left + right + 1) / 2;        // 修②：向上取整
        if (data[mid] <= target) left = mid;
        else right = mid - 1;
    }
    return data[left] == target ? left : -1;
}

修复对不对，拿数据砸。

四组边界用例：{1,2,2,2,3} 找 2 返回 3；{2,2,2} 找 2 返回 2；{1,2,3} 找 9 返回 -1；空数组返回 -1 且不崩溃。再加对拍：随机生成 20 万组长度 0~11 的升序数组与目标值，和「从头到尾扫一遍取最后命中」的暴力解逐组比对，0 组不一致。「边界用例 + 暴力对拍」这套动作比口头论证有力得多，面试时主动做出来是实打实的加分项。

回到笔试与面试现场，建议的答题结构：先别急着挑错，先复述代码意图并拆出循环骨架——区间怎么定义、mid 怎么取、边界怎么动，因为三处错误全长在骨架的接缝上；然后按「终止性 → 边界 → 特殊输入」的顺序排查：收缩不前进死循环、上界多给一格越界、空数组没人管崩溃；最后给修复并用边界用例自证。顺带一提，同批还有一篇把二分查找的常见变体整理成了模板坐标系，可以对照着看。你自己写二分时踩过最深的坑是哪一个？评论区聊聊。