Leetcode: 278. First Bad Version

思路

呼叫API的次数越少越好，因为不确定错误会是在前面一点的版本出现，还是後面一点的版本出现，因此最好从中间的版本切入，如果该版本回传结果为有错误的版本，则继续往前追溯；反之若回传为正确版本，则继续往後追溯，直到寻找的版本号边界交错。

是Binary search的应用题。

程序

class Solution {
public:
    int firstBadVersion(int n) {
        int bversion = -1;
        int lb = 0, ub = n;
        while( ub >= lb ) {
            int index = lb + (ub - lb) / 2;
            if ( isBadVersion(index) ) {
                ub = index - 1;
                bversion = index;
            }
            else
                lb = index + 1;
        }
        return bversion;
    }
};

打铁趁热的话

了解题目到写完程序，我花了10分钟，还是可以再更快一点> 口 <。