278. 第一个错误的版本

leetcode链接：
https://leetcode.cn/problems/first-bad-version/description/

方案一

int left = 0, 
	right = n, 
	mid = 0;

while (left < right) {
	mid =  left + (right - left) / 2;
	if (isBadVersion(mid)) {
		right = mid;
	} else {
		left =  mid + 1;
	}
}

return left;

结果

• 24/24 cases passed (13 ms)
• Your runtime beats 99.04 % of java submissions
• Your memory usage beats 22.52 % of java submissions (38.4 MB)

分析

时间复杂度：
O( log n )

空间复杂度：
O( 1 )

几乎最优方案

https://leetcode.cn/problems/first-bad-version/solution/di-yi-ge-cuo-wu-de-ban-ben-by-leetcode-s-pf8h/

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) { // 循环直至区间左右端点相同
            int mid = left + (right - left) / 2; // 防止计算时溢出
            if (isBadVersion(mid)) {
                right = mid; // 答案在区间 [left, mid] 中
            } else {
                left = mid + 1; // 答案在区间 [mid+1, right] 中
            }
        }
        // 此时有 left == right，区间缩为一个点，即为答案
        return left;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/first-bad-version/solution/di-yi-ge-cuo-wu-de-ban-ben-by-leetcode-s-pf8h/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。