First Bad Version（第一个错误的版本）

题目 / Problem

中文： 你是一名产品经理，正在带领团队开发一个新产品。不幸的是，产品的最新版本没有通过质量检查。由于每个版本都是基于前一个版本开发的，因此从某个错误版本开始，之后的所有版本也都会出错。

假设共有 n 个版本 [1, 2, ..., n]，请找出第一个错误的版本，因为它会导致后面的所有版本都出错。

题目提供了 API bool isBadVersion(version)，用于判断指定版本是否出错。请实现一个函数找出第一个错误版本，并尽量减少对该 API 的调用次数。

English: You are a product manager leading a team that is developing a new product. Unfortunately, the latest version fails the quality check. Since each version is developed from the previous version, every version after a bad version is also bad.

Suppose you have n versions [1, 2, ..., n]. Find the first bad version, which causes all following versions to be bad.

You are given an API bool isBadVersion(version) that returns whether a version is bad. Implement a function that finds the first bad version while minimizing calls to the API.

版本规律 / Version Pattern

所有版本的状态具有单调性：
The version states are monotonic:

版本 / Version:  1      2      3      4      5      ...      n
状态 / Status:  good   good   good   bad    bad     ...     bad
                                  ↑
                         第一个错误版本
                         First bad version

问题本质上是在一段由 false 变为 true 的有序序列中，寻找第一个 true。
The problem is equivalent to finding the first true in an ordered sequence that changes from false to true.

示例 / Examples

Example 1

Input:  n = 5, bad = 4
Output: 4

一种可能的 API 调用过程 / One possible API call sequence:
isBadVersion(3) -> false
isBadVersion(5) -> true
isBadVersion(4) -> true

因此第一个错误版本是 4。
Therefore, version 4 is the first bad version.

bad 只用于描述测试数据中第一个错误版本的位置，不会作为参数传入函数。
bad only describes the first bad version in the test data; it is not passed to the function.

Example 2

Input:  n = 1, bad = 1
Output: 1

约束 / Constraints

1 <= bad <= n <= 2³¹ - 1

解题思路：寻找左边界的二分查找 / Approach: Left-Boundary Binary Search

使用闭区间 [left, right] 保存第一个错误版本可能出现的范围：
Use the closed interval [left, right] to store the range that may contain the first bad version:

初始化 left = 1、right = n。
Initialize left = 1 and right = n.
当 left < right 时，计算中间版本 mid。
While left < right, calculate the middle version mid.
如果 isBadVersion(mid) 为 true，mid 可能就是第一个错误版本，因此保留它并令 right = mid。
If isBadVersion(mid) is true, mid may be the first bad version, so keep it and set right = mid.
如果结果为 false，说明 mid 及之前的版本都是好的，令 left = mid + 1。
If it is false, mid and every earlier version are good, so set left = mid + 1.
当 left === right 时，区间只剩一个版本，它就是第一个错误版本。
When left === right, the single remaining version is the first bad version.

JavaScript 实现 / JavaScript Implementation

/**
 * Definition for isBadVersion()
 *
 * @param {number} version
 * @return {boolean}
 * function isBadVersion(version) {}
 */

/**
 * @param {function} isBadVersion
 * @return {function}
 */
const solution = function (isBadVersion) {
  /**
   * @param {number} n Total versions
   * @return {number} The first bad version
   */
  return function (n) {
    let left = 1;
    let right = n;

    while (left < right) {
      const mid = left + Math.floor((right - left) / 2);

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

    return left;
  };
};

执行过程 / Walkthrough

以 n = 5、第一个错误版本为 4 为例，本实现的调用过程如下：
For n = 5 with version 4 as the first bad version, this implementation proceeds as follows:

步骤 / Step	`left`	`right`	`mid`	API 结果 / Result	更新 / Update
1	1	5	3	`false`	`left = 4`
2	4	5	4	`true`	`right = 4`

此时 left === right === 4，返回 4。该过程只调用了两次 API；示例中的调用顺序并不是唯一的。
Now left === right === 4, so return 4. This process uses only two API calls; the sequence shown in the example is not the only possible one.

为什么使用 `right = mid`？ / Why Use `right = mid`?

当 isBadVersion(mid) 返回 true 时，只能确定第一个错误版本位于 [left, mid] 中。mid 本身仍可能是答案，所以不能将它排除。
When isBadVersion(mid) returns true, the first bad version is known to lie in [left, mid]. Because mid itself may be the answer, it must not be discarded.

正确 / Correct:    right = mid
错误 / Incorrect:  right = mid - 1

相反，当 mid 是好版本时，根据单调性可以确定 [left, mid] 中没有答案，所以使用 left = mid + 1。
In contrast, when mid is good, monotonicity guarantees there is no answer in [left, mid], so use left = mid + 1.

为什么不会整数溢出？ / Why Avoid Integer Overflow?

版本号最大为 2³¹ - 1。在某些使用固定宽度整数的语言中，直接计算 (left + right) / 2 可能溢出，因此使用：
The largest version number is 2³¹ - 1. In languages with fixed-width integers, (left + right) / 2 may overflow, so use:

const mid = left + Math.floor((right - left) / 2);

JavaScript 的 Number 可以安全表示该约束范围内的整数，但这种写法仍具有更好的跨语言通用性。
JavaScript's Number safely represents integers in this range, but this form remains more portable across languages.

复杂度 / Complexity

时间复杂度：O(log n)，每次 API 调用后都将搜索范围缩小约一半。
Time: O(log n), because every API call reduces the search range by about half.
API 调用次数：O(log n)，最坏约为 ⌈log₂ n⌉ 次。
API calls: O(log n), at most approximately ⌈log₂ n⌉ calls.
空间复杂度：O(1)，只使用常数个额外变量。
Space: O(1), because only a constant number of extra variables is used.

与从版本 1 开始逐个调用 API 的 O(n) 解法相比，二分查找大幅减少了 API 调用次数。
Compared with an O(n) linear scan that calls the API from version 1 onward, binary search greatly reduces the number of API calls.

易错点 / Common Pitfalls

目标是找到第一个错误版本，不是任意一个错误版本。
Find the first bad version, not just any bad version.
当 mid 是错误版本时，应使用 right = mid，不能排除 mid。
When mid is bad, use right = mid; do not discard mid.
当 mid 是好版本时，应使用 left = mid + 1，否则可能无限循环。
When mid is good, use left = mid + 1 to avoid an infinite loop.
bad 不会传入函数，只能通过 isBadVersion() 获取版本状态。
bad is not passed to the function; version status is available only through isBadVersion().
返回值是版本号，版本编号从 1 开始，不是从 0 开始。
Return the version number; versions are numbered from 1, not 0.
注意中点计算可能产生的整数溢出问题。
Be mindful of potential integer overflow in midpoint calculations.

First Bad Version