First Bad Version

First Bad Version.png

===================== 解題思路 =====================

二分法檢查 如果 mid 的版本是 bad version 那說明至少 first bad version 會在 mid 或是 mid 之前 所以把範圍縮小到 right = mid, 反之則是 left = mid

===================== C++ code ====================

<pre><code>
/**

• class SVNRepo {

• public:
  

• static bool isBadVersion(int k);
  

• }
• you can use SVNRepo::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
    int left = 0, right = n;
    while(left + 1 < right)
    {
        int mid = left + (right - left) / 2;
        if(SVNRepo::isBadVersion(mid)) right = mid;
        else left = mid;
    }
    if(SVNRepo::isBadVersion(left)) return left;
    else return right;
}

};
<code><pre>