博文中会简要介绍Leetcode P0278题目分析及解题思路。

“First Bad Version”是比较简单的题目，利用二分搜索找到临界点即可。临界点特征是：比它更小的版本是鲁棒的，比它更大的版本是有漏洞的。这样的特征其实可以找到两个临界点，靠右的临界点是最早的出现漏洞的版本。

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.

基本思路就是，如果mid代表的版本有漏洞，则往后续版本寻找；否则则往前列版本寻找。

以下是Java的题解代码实现。

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1, right = n, mid = left+(right-left)/2;
        while (left < right) {
            if (isBadVersion(mid)) {
                right = mid-1;
            }
            else {
                left = mid+1;
            }
            
            mid = left+(right-left)/2;
        }
        
        return isBadVersion(mid)? mid: mid+1;
    }
}

以下是C++的题解代码实现。

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1, right = n, mid = left+(right-left)/2;
        while (left < right) {
            if (isBadVersion(mid)) {
                right = mid-1;
            }
            else {
                left = mid+1;
            }
            
            mid = left+(right-left)/2;
        }
        
        return isBadVersion(mid)? mid: mid+1;
    }
};