First Bad Version

The code base version is an integer start from 1 to n. One day, someone committed a bad version in the code case, so it caused this version and the following versions are all failed in the unit tests. Find the first bad version.

http://www.lintcode.com/en/problem/first-bad-version/

Discussion

典型的二分，没啥好说的了。唯一注意的是是从1到n。

Solution

/**
 * class VersionControl {
 *     public:
 *     static bool isBadVersion(int k);
 * }
 * you can use VersionControl::isBadVersion(k) to judge whether 
 * the kth code version is bad or not.
*/
class Solution {
public:
    /**
     * @param n: An integers.
     * @return: An integer which is the first bad version.
     */
    int findFirstBadVersion(int n) {
        // write your code here
        if(n==1) return 1;
        int start = 1;
        int end = n;
        while (start +1 < end) {
            int mid = start + (end-start)/2;
            if(vsControl.isBadVersion(mid) == true) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if(vsControl.isBadVersion(start) == true)
            return start;
        if(vsControl.isBadVersion(end) == true)
            return end;
    }
private:
    VersionControl vsControl;
};