[Leetcode 278] First Bad Version

作者 Shilei Tian 日期 2016-04-18
[Leetcode 278] First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

这道题看起来确实比较简单,对于题目的要求,显然使用二分查找即可,代码如下:

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
int start = 1, end = n;
while (start < end) {
int mid = (start + end) / 2;
if (isBadVersion(mid)) {
end = mid;
} else {
start = mid + 1;
}
}
return start;
}
};

提交的时候肯定心想,擦,怎么这么简单,为什么通过率还这么低(22.4%)?但是系统给出的是 Time Limit Exceeded。What?为什么会这个样子?再想一下,这个思路应该没有错啊。先看看正确的代码:

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
int start = 1, end = n;
while (start < end) {
int mid = start + (end - start)/2; // 差距就在这儿!!
if (isBadVersion(mid)) {
end = mid;
} else {
start = mid + 1;
}
}
return start;
}
};

结合着系统给出的错误信息:

2126753390 versions 1702766719 is the first bad version.

仔细琢磨它给出的数字,再想一下 INT_MAX = 2147483647,就可以想到的是,可能会越界。实际上,如果用第一种求解中点的办法,确实可能会越界,比如当 start = 1063376695(这个数是第一次迭代的 mid 值),end = 2126753390,这样 start + end = 3190130085,确实超过了 INT_MAX 的值,最终 mid 值会因为溢出导致求解到一个负数。因此我们就需要将求解中点的方法修改一下,才不会越界。

这道题道理很简单,但是这种细节很容易被忽视。看样子全球大部分的朋友一开始的时候都没有注意到这个细节,才使得这个二分查找的题目通过率如此低!