You are a product manager and currently leading a team to develop a new product. 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.
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.
Binary search to find the first bad version. If mid is bad, search left; else search right.
1public class Solution extends VersionControl {
2 public int firstBadVersion(int n) {
3 int left = 1, right = n;
4
5 while (left < right) {
6 int mid = left + (right - left) / 2;
7 if (isBadVersion(mid)) {
8 right = mid;
9 } else {
10 left = mid + 1;
11 }
12 }
13
14 return left;
15 }
16}