LeetCode 278. 第一个错误的版本

Categories:

题目描述
思路分析
1. 解法一：二分查找（推荐）
相似题目

题目描述

✅ 278. 第一个错误的版本

思路分析

解法一：二分查找（推荐）

核心思路：

第一个错误版本满足单调性：错误版本之后全是错误。

用二分查找第一个满足 isBadVersion 的位置。

收缩区间时保持答案在 [left, right] 内。

复杂度分析：

时间复杂度：O(log n)，其中 n 表示版本数量。

空间复杂度：O(1)，仅使用常数额外空间。

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
}

func firstBadVersion(n int) int {
	left, right := 1, n

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

	return left
}

相似题目

题目	难度	考察点
35. 搜索插入位置	简单	二分查找
33. 搜索旋转排序数组	中等	二分查找
153. 寻找旋转排序数组中的最小值	中等	二分查找
704. 二分查找	简单	二分模板
374. 猜数字大小	简单	二分查找

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/35656737