LeetCode 278. 第一个错误的版本

2021-03-14 HGNULB 约 9 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 278. 第一个错误的版本

题意分析

有 1 到 n 共 n 个版本，其中某个版本开始出了问题，它之后的所有版本都是错的。只能通过调用接口 isBadVersion(version) 来问「这个版本是不是坏的」，要求找出第一个坏版本的编号，并且尽量减少调用次数。

「之后全坏」这句话是整道题的题眼。它意味着把版本序列写成布尔数组，形状必然是若干个 false 后面跟着若干个 true，中间不会交错。这种只翻转一次的布尔序列具备严格的单调性，是可以对下标做折半查找的充分条件。

「尽量减少调用次数」是在明确否定从 1 开始逐个试探的 $O(n)$ 做法。题目把接口调用当作昂贵操作来计费，这是交互式二分题的典型包装。

还要注意 n 的上界是 $2^{31} - 1$，也就是 int 的最大值。这直接决定了求中点时不能写 (left + right) / 2——两个接近 $2^{31}$ 的数相加会溢出成负数。这是本题除二分边界外唯一的实现陷阱，也是它被反复拿来考的原因。

题目保证答案一定存在（至少有一个坏版本），所以不必考虑「全是好版本」的情况。边界要想的是 n = 1（答案只能是 1）、第一个版本就坏、以及最后一个版本才坏这三种。

解法：二分查找判定答案

核心思路

朴素做法是从版本 1 开始依次调用 isBadVersion，第一个返回 true 的就是答案。正确但要调用最多 $n$ 次，在 $n$ 接近 21 亿时完全不可接受。

瓶颈在于每次调用只排除了一个候选。而利用「坏版本之后全坏」这条单调性，一次调用可以排除一半候选：如果 isBadVersion(mid) 为真，说明答案就是 mid 或在它左边（mid 右边的版本虽然也都坏，但都不是「第一个」）；如果为假，说明 mid 及其左边全是好的，答案严格在 mid 右边。

这就把问题从「查找某个值」变成了查找布尔序列中第一个 true 的位置，也就是二分的「找左边界」形态。

维护的不变量是：第一个坏版本始终落在闭区间 [left, right] 内。初始时区间是 [1, n]，题目保证答案存在，成立。每一轮取中点 mid：若 mid 是坏的，它本身就是一个合法候选，所以收缩成 right = mid（不能是 mid - 1，那会把答案本身丢掉）；若 mid 是好的，它一定不是答案，收缩成 left = mid + 1。两支都保证了答案仍在新区间内，不变量得以维持。

循环条件用 left < right，退出时 left == right，区间收缩成唯一一个元素，由不变量它就是答案，直接返回 left 即可，不需要在循环外再调用一次 isBadVersion 确认。

这个写法还有一个不易察觉但很关键的性质：mid 取的是向下取整的中点，所以 mid < right 恒成立，right = mid 一定让区间真正变小；同时 left = mid + 1 显然也在变小。两支都严格收缩，循环必然终止。如果把 mid 改成向上取整，right = mid 这一支在区间只剩两个元素时会原地不动，直接死循环——这是「找左边界用下取整、找右边界用上取整」这条口诀的由来。

解题步骤

区间初始化为 [1, n]：版本编号从 1 开始而不是 0，写成 left = 0 会让答案可能落在一个不存在的版本上。区间含义是闭区间「答案可能在这里面」。

循环条件写 left < right：这里刻意不用 left <= right。因为不变量保证了答案必在区间内，当区间收缩到只剩一个元素时就已经确定了答案，无需再判定一次；用 <= 则需要额外的变量记录候选答案，写法更啰嗦也更容易出错。

中点写成 left + (right - left) / 2：n 可以取到 int 上限，left + right 会溢出为负数，nums[mid] 或 isBadVersion(mid) 拿到负参数会直接出错。这个写法先做减法保证不越界，是本题必须写对的一行。

isBadVersion(mid) 为真时 right = mid：mid 自身仍是候选，必须保留在区间里。写成 mid - 1 会在「mid 恰好就是第一个坏版本」时把正确答案排除掉。

为假时 left = mid + 1：mid 已被确认是好的，可以安全排除；写成 left = mid 会让区间在只剩两个元素时不再收缩，造成死循环。

返回 left：退出循环时 left == right，返回哪个都一样，返回 left 更符合「找左边界」的语义。

以 n = 5、第一个坏版本是 4 走一遍（即 isBadVersion 对 1、2、3 返回假，对 4、5 返回真）。

初始：left = 1、right = 5，答案 4 在区间内。

第一轮：mid = 1 + (5-1)/2 = 3。isBadVersion(3) 为假，说明 1~3 全好，left = 4。区间变成 [4, 5]，答案仍在内。

第二轮：mid = 4 + (5-4)/2 = 4。isBadVersion(4) 为真，mid 是候选，right = 4。区间变成 [4, 4]。

left == right，循环退出，返回 4。全程只调用了 2 次接口，而线性扫描需要 4 次。

注意第二轮里如果把 right = mid 误写成 right = mid - 1，区间会变成 [4, 3]，left > right 使循环立刻退出并返回 left = 4——这个用例居然碰巧还对，但换成 n = 2、第一个坏版本是 2 的用例：mid = 1 为假，left = 2，退出返回 2，也对；再换成 n = 2、第一个坏版本是 1：mid = 1 为真，若写 right = 0，区间变成 [2, 0]，退出后返回 left = 2，答案错误。可见这个 bug 只在特定形状下暴露，必须靠不变量而不是靠试用例来保证正确。

再验证两个边界。n = 1：left == right == 1，循环一次都不进，直接返回 1，正确。n = 5、第一个坏版本是 1：第一轮 mid = 3 为真 → right = 3；第二轮 mid = 2 为真 → right = 2；第三轮 mid = 1 为真 → right = 1，退出返回 1，正确。

代码实现

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;

        // 区间内始终保留第一个错误版本这个答案。
        while (left < right) {
            int mid = left + (right - left) / 2;

            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
}

func firstBadVersion(n int) int {
    // 用二分查找第一个满足 isBadVersion 的位置。
    left, right := 1, n

    for left < right {
        mid := left + (right-left)/2
        if isBadVersion(mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }

    return left
}

复杂度分析

时间复杂度：$O(\log n)$，其中 $n$ 是版本总数。每轮调用一次 isBadVersion 并把候选区间的长度砍掉一半，从 $n$ 缩到 1 需要 $\lceil \log_2 n \rceil$ 轮。$n$ 取到 $2^{31}-1$ 时也只要 31 次调用。

空间复杂度：$O(1)$，只用了 left、right、mid 三个整型变量，没有递归也没有额外结构。若写成递归版则栈深度为 $O(\log n)$，但没有必要。

关键点总结

二分的适用前提不是「数组有序」，而是存在一个关于位置单调的布尔判定。本题的判定是 isBadVersion，一旦为真就永远为真，这种 false...false true...true 的形状就是「二分答案」类题目的通用信号。

「找第一个满足条件的位置」用 while (left < right) + right = mid / left = mid + 1 + 返回 left 这一套模板；把 mid 取下取整是模板成立的必要条件，否则会死循环。记模板不如记住「哪一支保留 mid、mid 就要偏向哪一侧」。

判断边界更新是否正确的唯一可靠方法是写出区间不变量（这里是「答案始终在 [left, right] 里」）并逐支验证，靠试样例往往会被幸运用例蒙混过去。

left + (right - left) / 2 不是可选的优化而是必需的写法，只要上界接近 int 极限就必须这么写；面试官经常特意把 n 设成 2^31 - 1 来考这一点。

调用外部接口的题目要有「调用是昂贵操作」的意识：本解法每轮只调用一次并复用结果，若在一轮里重复调用 isBadVersion(mid) 两次，复杂度常数直接翻倍。

易错点总结

中点写成 (left + right) / 2：n = 2147483647 时第一轮 left + right 就溢出成负数，isBadVersion 收到负版本号直接异常或返回错误结果。

isBadVersion(mid) 为真时写 right = mid - 1：n = 2、第一个坏版本是 1 时，mid = 1 为真使 right = 0，退出后返回 left = 2，把唯一正确的答案排除了。

为假时写 left = mid：区间剩下 [3, 4] 且 3 是好的时，mid = 3、left 仍是 3，区间不再收缩，死循环。

循环条件写成 left <= right 却仍返回 left：n = 1 时会多进一轮，right 被更新成 0，虽然返回值碰巧还是 1，但在 left = mid + 1 分支下 left 可能越过 n，返回一个不存在的版本号。

区间初始化成 [0, n] 或 [1, n-1]：版本编号是 1 到 n，前者会让 isBadVersion(0) 被调用，后者在「只有最后一个版本是坏的」时永远够不到答案。

循环体里调用两次 isBadVersion(mid)（比如 if (isBadVersion(mid)) ... else if (!isBadVersion(mid)) ...）：结果正确但调用次数翻倍，交互题里这属于实打实的性能问题。

退出循环后再调用一次 isBadVersion(left) 做确认并在为假时返回 left + 1：不变量已经保证 left 就是答案，多这一步不仅浪费一次调用，在 left 已是 n 时还可能返回 n + 1 这个不存在的版本。

从 1 开始线性试探：n 接近 21 亿时需要上亿次接口调用，必然超时，这正是题目强调「减少调用次数」要否定的做法。

误以为坏版本可能不连续：如果按「找任意一个坏版本」来写，n = 5、坏版本从 2 开始时可能返回 3 或 4，而题目要的是第一个。

用 mid 而不是 left 作为返回值：退出循环时 mid 停留在最后一次计算的位置，未必等于 left，n = 2、答案为 2 时 mid 是 1 而 left 是 2，直接返回错误答案。

相似题目

题目	难度	考察点
704. 二分查找	简单	查找确定值而非边界，命中即可返回，用 `left <= right` 的闭区间模板
35. 搜索插入位置	简单	同为找左边界，但判定条件是 `nums[mid] >= target`，且答案可能落在数组末尾之后
34. 在排序数组中查找元素的第一个和最后一个位置	中等	需要左右两次二分，右边界的模板要改用上取整避免死循环
367. 有效的完全平方数	简单	在值域而非下标上二分，判定条件是 `mid * mid >= num`，需注意乘法溢出
540. 有序数组中的单一元素	中等	单调性藏在「配对下标的奇偶性」里，需先构造判定条件才能二分
剑指 Offer 53 - II. 0～n-1中缺失的数字	简单	判定条件是 `nums[mid] != mid`，同样是找第一个为真的位置
剑指 Offer 53 - I. 在排序数组中查找数字 I	简单	用左右边界相减得到出现次数，是本题模板的直接组合应用
LCR 068. 搜索插入位置	简单	与 35 同题
LCR 070. 有序数组中的单一元素	中等	与 540 同题
面试题 10.05. 稀疏数组搜索	简单	数组含空串导致比较失效，需在 `mid` 附近线性挪动后再二分