第一个错误的版本 图解题解

第一个错误的版本这道题在找什么

有 n 个版本，编号 1 到 n，从某个版本起坏，且一旦坏就之后全坏。你只有一个接口 isBadVersion(v)，问它第 v 版坏没坏、坏就返回 true。要找出第一个坏版本的编号，且调用次数尽量少。题面例子：n=5、第 4 版起坏，答案是 4。

为什么从头一个个问会太慢

从版本 1 挨个问 isBadVersion(1)、isBadVersion(2)……问到第一个返回 true 就停，能找到，但最坏要问将近 n 次；n 是十亿就得问接近十亿次，等不起。根子是没用上「一旦坏则之后全坏」这个结构——版本排得很有规律，逐个扫却当它杂乱一堆。

为什么这道题能二分

「一旦坏则之后全坏」意味着版本前一段全好、后一段全坏，中间只翻一次脸：「好好好坏坏坏」。isBadVersion 的返回值也从 false 变成 true、只翻这一次，是一条 false…false true…true 的分界。找第一个坏版本，就是找这条分界上第一个 true 的位置（这类『找第一个满足条件的下标』叫 lower_bound）。有这种单调（一个方向到底、不回头）结构，就能二分查找，不必逐格看。

mid 坏往哪边收、mid 好往哪边收

候选区间 [l, r]，l 左边界、r 右边界，第一个坏版本一定夹在中间。每轮取中点 mid（区间正中那个编号，取 l+(r-l)//2），只问一次 isBadVersion(mid)。它坏：答案是 mid 或在它左边，右边界收到 r = mid——是 mid 不是 mid-1，mid 自己可能就是答案、减一会丢掉它。它好：答案在 mid 右边，mid 连同左边全排除，l 推到 mid+1。答案始终在 [l, r] 内，循环到 l 和 r 撞在一起就是答案。

n=5、第 4 版起坏，逐问缩区间

版本坏好是「好好好坏坏」，l=1、r=5。第一轮 mid = 1+(5-1)//2 = 3，问 isBadVersion(3)，版本 3 好，于是 l = 3+1 = 4。第二轮区间剩 [4, 5]，mid = 4+(5-4)//2 = 4，问 isBadVersion(4)，版本 4 坏，于是 r = 4。此时 l、r 都等于 4，循环停下，返回 4。整趟只问了 2 次 isBadVersion。

右界多减一，就吞掉第一个坏版本

mid 坏说明答案在 mid 或更左，写成 r = mid-1 就等于断定 mid 不是答案、把它踢出区间，真答案恰是 mid 时就返回成它右边那个，错。好版本那支 l 必须是 mid+1，漏了加一、让 l 停在 mid，好版本还赖在区间里，区间永远缩不动，直接死循环。还有 mid 一律用 l+(r-l)//2，别写 (l+r)//2，l、r 接近整型上限时相加会溢出。这三处对了，每问一次砍掉一半候选，次数就是 O(log n)，n=10 亿也不过约 30 次；只用 l、r、mid 三个变量，空间 O(1)。

Python

def firstBadVersion(n):
    l, r = 1, n                 # 候选区间 [l, r]
    while l < r:
        mid = l + (r - l) // 2  # 防溢出的取中点
        if isBadVersion(mid):   # mid 坏：答案在它或它左边
            r = mid             # 不能丢掉 mid，所以是 mid 不是 mid-1
        else:                   # mid 好：答案在它右边
            l = mid + 1
    return l                    # l == r 时即第一个坏版本

C++

int firstBadVersion(int n){
    int l = 1, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (isBadVersion(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

Java

public int firstBadVersion(int n) {
    int l = 1, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (isBadVersion(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}