此题就是二分的变种,但是千万要注意大整数求和越界,正确的计算方式应该是 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 &gt;= right) { return right; } long long middle = (left + right) / 2; if (!isBadVersion(middle)) { if (middle + 1 &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>};