題目： LeetCode - 278. First Bad Version

題目說明

給一個整數 n，求 1, 2, …, n 中，從哪個數字開始是 Bad version。

解題思路

使用二元搜尋法即可。
※ 須注意溢位的問題，所以型態使用 long long。

參考解法

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int firstBadVersion(int n) {
        long long first = 1, last = n, mid = (first + last) / 2;
        while(!isBadVersion(mid) || isBadVersion(mid - 1))
        {
            if(!isBadVersion(mid))
                first = mid + 1;
            else
                last = mid - 1;
            mid = (first + last) / 2;
        }
        return mid;
    }
};