278. 第一个错误的版本
描述
- 你是产品经理，目前正在领导一个团队开发一个新产品。不幸的是，您的产品的最新版本没有通过质量检查。由于每个版本都是基于之前的版本开发的，所以错误版本之后的所有版本都是不好的。
说明
- 假设你有 n 个版本 [1, 2, ..., n]，你想找出第一个错误的版本，导致下面所有的错误。
- 你可以通过 bool isBadVersion(version) 的接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。您应该尽量减少对 API 的调用次数。
思路
- 题目进行了一个包装，本质就是在排序的列表中找到一个数，因此利用二分查找即可。
- 要注意与二分查找不同的是 end = mid 而不是 mid - 1。每次找到的BadVesion是一个待选版本，不能抛弃。
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
class Solution_278 {
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 == end ? start : -1;
}
};
