278. 第一个错误的版本
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例:
给定 n = 5，并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false调用 isBadVersion(5) -> true调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
二分法，注意边界。
不能写 int mid = (lo + hi) / 2; 要写 int mid = lo + (hi - lo) / 2;
这个题目，返回 lo 或者 hi 都行，因为终止条件是 lo == hi.这是二分里比较难的题目了吧，找的是分割点，不是某个值。[****########] 就像这样的有序数组，找第一个 # 号。二分搜索的演化版本，查找某个值，返回其索引，如果找不到，返回其本来应该所在的位置（比如上面 # 号的位置）。遇到这种二分搜索，就拿这个 bad version 来套就行了。
boolisBadVersion(intversion);
classSolution {
public:
intfirstBadVersion(intn) {
intlo=1, hi=n;
while(lo<hi) {
intmid=lo+ (hi-lo) /2;
if (isBadVersion(mid)) {
hi=mid;
} else {
lo=mid+1;
}
}
returnhi;
}
};
不在循环内定义零时变量
执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗 :8.3 MB, 在所有 C++ 提交中击败了5.38%的用户
intfirstBadVersion(intn) {
intlow=1;
intmid=low+(n-low ) /2;
while (low<n)
{
if (isBadVersion(mid))
{
n=mid;
}
else
{
low=mid+1;
}
mid=low+(n-low ) /2;
}
returnlow;
}
