First Bad Version
最后更新于：2022-04-02 01:08:56
# First Bad Version
### Source
- lintcode: [(74) First Bad Version](http://www.lintcode.com/en/problem/first-bad-version/)
### Problem
The code base version is an integer start from 1 to n. One day, someonecommitted a bad version in the code case, so it caused this version and thefollowing versions are all failed in the unit tests. Find the first badversion.
You can call `isBadVersion` to help you determine which version is the firstbad one. The details interface can be found in the code's annotation part.
#### Example
Given n = `5`:
~~~
isBadVersion(3) -> false
isBadVersion(5) -> true
isBadVersion(4) -> true
~~~
Here we are 100% sure that the 4th version is the first bad version.
#### Note
Please read the annotation in code area to get the correct way to callisBadVersion in different language. For example, Java is`VersionControl.isBadVersion(v)`
#### Challenge
You should call *isBadVersion* as few as possible.
### 题解
基础算法中 [Binary Search](http://algorithm.yuanbin.me/zh-cn/basics_algorithm/binary_search.html) 的 lower bound. 找出满足条件的下界即可。
### Python
~~~
#class VersionControl:
# @classmethod
# def isBadVersion(cls, id)
# # Run unit tests to check whether verison `id` is a bad version
# # return true if unit tests passed else false.
# You can use VersionControl.isBadVersion(10) to check whether version 10 is a
# bad version.
class Solution:
"""
@param n: An integers.
@return: An integer which is the first bad version.
"""
def findFirstBadVersion(self, n):
lb, ub = 0, n + 1
while lb + 1 < ub:
mid = lb + (ub - lb) / 2
if VersionControl.isBadVersion(mid):
ub = mid
else:
lb = mid
return lb + 1
~~~
### C++
~~~
/**
* class VersionControl {
* public:
* static bool isBadVersion(int k);
* }
* you can use VersionControl::isBadVersion(k) to judge whether
* the kth code version is bad or not.
*/
class Solution {
public:
/**
* @param n: An integers.
* @return: An integer which is the first bad version.
*/
int findFirstBadVersion(int n) {
int lb = 0, ub = n + 1;
while (lb + 1 < ub) {
int mid = lb + (ub - lb) / 2;
if (VersionControl::isBadVersion(mid)) {
ub = mid;
} else {
lb = mid;
}
}
return lb + 1;
}
};
~~~
### Java
~~~
/**
* public class VersionControl {
* public static boolean isBadVersion(int k);
* }
* you can use VersionControl.isBadVersion(k) to judge whether
* the kth code version is bad or not.
*/
class Solution {
/**
* @param n: An integers.
* @return: An integer which is the first bad version.
*/
public int findFirstBadVersion(int n) {
int lb = 0, ub = n + 1;
while (lb + 1 < ub) {
int mid = lb + (ub - lb) / 2;
if (VersionControl.isBadVersion(mid)) {
ub = mid;
} else {
lb = mid;
}
}
return lb + 1;
}
}
~~~
### 源码分析
lower bound 的实现，这里稍微注意下lb 初始化为 0，因为 n 从1开始。ub 和 lb 分别都在什么条件下更新就好了。另外这里并未考虑 `n <= 0` 的情况。
### 复杂度分析
二分搜索，O(logn)O(\log n)O(logn).
';