278. First Bad Version

解題思路

覺得這題題目的 input 敘述沒寫好。input 寫會給 n 跟 bad，害我想好久都給 bad 了是要解甚麼。

題目可簡化為有一個長度為 n 的 array，長這樣：[0, 0, 0, ......, 1, 1]。問：第一個 1 在哪個位置？輸入給定 array 的長度，以及提供 isBadVersion(n) 的 API，以使用 API 次數最少的方法求解。

算是 binary search 的變化版？

另外由於 mid 直接 (left + right)/2 會太大，必須換一種寫法。

程式碼

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1, right = n;
        while(left < right)
        {
            int mid = left + (right - left)/2;
            if(isBadVersion(mid))
                right = mid;
            else
                left = mid + 1;
        }
        return left;
    }
};