278第一个错误的版本

Jul 2, 2024

练习次数 **

      简单 │ 1014  │ 45.7% 的 1.1M

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

󰛨 示例 1：

│ 输入：n = 5, bad = 4
│ 输出：4
│ 解释：
│ 调用 isBadVersion(3) -> false
│ 调用 isBadVersion(5) -> true
│ 调用 isBadVersion(4) -> true
│ 所以，4 是第一个错误的版本。

󰛨 示例 2：

│ 输入：n = 1, bad = 1
│ 输出：1

 提示：

* 1 <= bad <= n <= 2^31 - 1



func firstBadVersion(n int) int {
 left, right := 1, n+1
 for left < right {
  middle := left + (right-left)/2
  if !isBadVersion(middle) {
   left = middle + 1
  } else if isBadVersion(middle) {
   right = middle
  }
  if middle == left+(right-left)/2 {
   return middle
  }
 }
 return right
}

// @leet end
解释这个解法

🤖:[ChatGPT4]
好的，我们一步一步来！

### 问题的目标:
找到导致之后所有版本出错的第一个错误的版本。

### 给定的前提条件:
1. `isBadVersion(version)` 是一个接口，它会返回一个布尔值，确定是否版本号 `version` 出错。
2. 我们需要尽量减少调用 `isBadVersion` 接口的次数。

### 使用的方法:
二分查找（Binary Search）

### 为何选择二分查找:
二分查找的时间复杂度是 O(log n)，相比普通遍历 O(n) 更高效。

### 代码解释:

我们处理的范围是 `[1, n]`：

``` go
func firstBadVersion(n int) int {
 left, right := 1, n+1
 for left < right {
  // 取中间的值
  middle := left + (right-left)/2

  // 若 middle 版本没有问题，则所有 < middle 版本也没有问题，将搜索范围缩小到 [middle + 1, right-1]
  if !isBadVersion(middle) {
   left = middle + 1
  } else if isBadVersion(middle) { // 若 middle 版本有问题，则它有可能是第一个错误的版本. 将搜索范围缩小到 [left, middle]
   right = middle
  }

  // 如果中间值保持不变，那么就表明我们已经找到第一个错误的版本
  if middle == left+(right-left)/2 {
   return middle
  }
 }
 return right
}

深入的逐行解释

初始化left 和 right，分别为 1 和 n + 1 。（right 设为 n + 1 是为了方便后面 mid 计算，但不常见）
在 left < right 范围内循环:
- middle := left + (right - left) / 2: 计算中间值，并防止溢出。
- if !isBadVersion(middle): 如果 middle 版本没有问题，这意味着第一个错误的版本在 middle 右边。所以更新 left = middle + 1。
- else: 否则中间版本有问题，所以错误的版本在 left ≤ middle 范围里。更新 right = middle。
if middle == left + (right - left) / 2: 如果 mid 值不再改变，那就说明我们已经锁定了第一个错误版本，并返回 middle。

检查内联变动更新

尽管设定为right = n + 1在某种条件下有效，但可能引起不必要的混淆，因为这个变动可能引入一个额外的特殊情况进行检查，例如right = right-1时不要被访问。为了优化并确保正确理解，我们更改为经典版本，并简化如下：

改进后的答案（样式改进）：

func firstBadVersion(n int) int {
 left, right := 1, n
 for left < right {
  middle := left + (right - left) / 2
  if !isBadVersion(middle) {
   left = middle + 1
  } else {
   right = middle
  }
 }
 return left  // 此时, left == right 是第一个错误版本所在位置
}

这样既减少误解，又明确了第一个错误版本的查找方式。那么，你更容易理解且易于扩展使用。