LeetCode 278. First Bad Version

做点简单的题目练练手，最近天天在写Scope脚本，都快忘记怎么写其他代码了。
吐槽一下垃圾长城宽带，上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 will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

分析

这其实就是个变种的二分查找，只要注意找到一个bad version的时候，往前多看一个版本就能决定是否要继续二分下去了。

代码

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
class Solution {
public:
    int firstBadVersion(int n) {
        int low = 1;
        int high = n;
        while(true){
            int mid = low + (high - low)/2;
            if(isBadVersion(mid)){
                //Look for previous cases
                bool isBad = isBadVersion(mid);
                if(isBad){
                    if(mid == 1)
                        return mid;
                    if(!isBadVersion(mid-1))
                        return mid;
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } else {
                low = mid + 1;
            }
        }
    }
};