首页 » 编程之美 » 正文

[leetcode]First Bad Version

此题就是二分的变种,但是千万要注意大整数求和越界,正确的计算方式应该是 left + (right – left) / 2; 我使用的是long long.

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);</p>

<p>class Solution {
public:
    int bSearch(long long left, long long right) {
        if (left &amp;gt;= right) {
            return right;
        }
        long long middle = (left + right) / 2;
        if (!isBadVersion(middle)) {
            if (middle + 1 &amp;gt; right) return middle;
            if (isBadVersion(middle+1)) return middle+1;
            else return bSearch(middle, right);
        }
        else {
            return bSearch(left, middle);
        }</p>

<pre><code>}
int firstBadVersion(int n) {        
    return bSearch(1, n);
}
</code></pre>

<p>};

发表评论