LeetCode - FirstBadVersion
by ne on 2022-02-16 under Algo/DS/Problems tagged with leetcode
/**
* 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 returns whether version is bad.
* Implement a function to find the first bad version. You should minimize the number of calls to the API.
*
* Example 1:
*
* Input: n = 5, bad = 4
* Output: 4
* Explanation:
* call isBadVersion(3) -> false
* call isBadVersion(5) -> true
* call isBadVersion(4) -> true
* Then 4 is the first bad version.
*/
public class FirstBadVersion {
// this method is provided by leetcode , adding dummy logic here.
static boolean isBadVersion(int m) {
return false;
}
public int firstBadVersion(int n) {
int b = 1;
int e = n;
while (b < e) {
int m = b + (e - b) / 2;
if (isBadVersion(m)) {
e = m;
} else {
b = m + 1;
}
}
return b;
}
}