First Bad Version
最后更新于：2022-04-01 22:58:10
**一. 题目描述**
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.
**二. 题目分析**
题目说了一堆，一开始并不知道是想让干什么。后来去网上查了题意，引用如下：
你是一名产品经理，并领导团队开发一个新产品。不幸的是，产品的最终版本没有通过质量检测。由于每一个版本都是基于上一个版本开发的，因此某一个损坏的版本之后的所有版本全都是坏的。
假设有n个版本[1, 2, …, n]，现在你需要找出第一个损坏的版本，它导致所有后面的版本都坏掉了。
提供给你一个API `bool isBadVersion(version)`，其功能是返回某一个版本是否损坏。实现一个函数找出第一个损坏的版本。你应该最小化调用API的次数。
原来只需实现类似于[Search for a Range](http://blog.csdn.net/liyuefeilong/article/details/50403616) 的功能，判断坏版本的函数`bool isBadVersion(version)`题目已经提供，无需纠结如何操作，这里还是使用二分查找来解决问题。
**三. 示例代码**
期初使用如下代码一直提示：Time Limit Exceeded
~~~
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
int low = 1, high = n;
int midIndex = 0;
while (low <= high)
{
midIndex = (low + high) / 2;
if (isBadVersion(midIndex))
high = midIndex - 1;
else
low = midIndex + 1;
}
return low;
}
};
~~~
检查了一段时间，发现当n取很大的数时出现问题，原来是语句`midIndex = (low + high) / 2;` 直接相加时溢出，导致循环超时，该用以下代码Accept。
~~~
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
int low = 1, high = n;
int midIndex = 0;
while (low <= high)
{
midIndex = low + (high - low) / 2;
if (isBadVersion(midIndex))
high = midIndex - 1;
else
low = midIndex + 1;
}
return low;
}
};
~~~
**四. 小结**
该题的难度在[Search for a Range](http://blog.csdn.net/liyuefeilong/article/details/50403616) 之下，但出现了数据溢出的问题，因此对于简单一些的题也时刻不能掉以轻心啊。
';