LeetCode 278. 第一个错误的版本 解析
这个问题要求找到第一个错误的版本，其中给定一个 API isBadVersion(version) 可以判断某个版本是否错误。由于版本号是有序的，且错误版本之后的所有版本都是错误的，因此可以使用二分查找高效地定位第一个错误版本。
方法思路
-
二分查找框架：
初始化左右指针left和right分别指向第一个和最后一个版本。
在每次循环中，计算中间版本mid，并调用isBadVersion(mid)判断：- 若
mid是错误版本，说明第一个错误版本在mid或其左侧，更新right = mid。 - 若
mid不是错误版本，说明第一个错误版本在mid右侧，更新left = mid + 1。
- 若
-
终止条件：
当left和right相遇时，循环结束，此时left即为第一个错误版本。
C++ 代码实现
// The API isBadVersion is already defined for you.
// bool isBadVersion(int version);class Solution {
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; // 错误版本在 mid 或其左侧} else {left = mid + 1; // 错误版本在 mid 右侧}}return left; // 循环结束时，left 即为第一个错误版本}
};
代码解释
-
二分查找初始化：
left = 1和right = n分别表示版本范围的左右边界。 -
防止整数溢出：
使用mid = left + (right - left) / 2代替mid = (left + right) / 2，避免当left和right都很大时发生整数溢出。 -
循环条件：
while (left < right)确保循环在left和right相遇时终止。 -
条件判断：
- 若
isBadVersion(mid)为真，说明第一个错误版本在[left, mid]范围内，更新right = mid。 - 若为假，说明第一个错误版本在
[mid+1, right]范围内，更新left = mid + 1。
- 若
-
返回结果：
循环结束时，left和right指向同一个位置，即第一个错误版本。
复杂度分析
- 时间复杂度：O(log n)，每次迭代将搜索范围缩小一半。
- 空间复杂度：O(1)，只需要常数级额外空间。
示例
假设 n = 5，且第一个错误版本是 4。
二分查找过程如下：
- 初始：
left = 1,right = 5,mid = 3isBadVersion(3)返回false→left = 4。
- 第二次迭代：
left = 4,right = 5,mid = 4isBadVersion(4)返回true→right = 4。
- 终止条件：
left == right == 4，返回4。
关键点
-
二分查找变体：
与传统二分查找不同，这里的right指向错误版本，因此更新时直接将right = mid，而非mid - 1。 -
防止溢出：
使用left + (right - left) / 2计算中间值，避免整数溢出。 -
循环终止条件：
left < right确保不会陷入死循环，且最终left即为所求结果。
这种方法高效且简洁，是解决有序数组中查找特定元素问题的经典思路。
在二分查找解决“第一个错误版本”问题时，while (left < right) 循环的设计是为了精准收缩搜索范围，最终让 left 和 right 相遇在目标位置（第一个错误版本）。以下从逻辑推导和实例验证两方面详细解释：
核心逻辑：范围收缩的必然性
二分查找的本质是通过不断排除不可能的范围，最终将搜索范围缩小到唯一解。在“第一个错误版本”问题中：
-
范围的单调性：
题目明确“错误版本之后的所有版本都是错误的”，即版本序列具有单调性：
[正确版本, 正确版本, ..., 第一个错误版本, 错误版本, ..., 错误版本]
这种单调性保证了二分查找的可行性。 -
循环条件
left < right的作用：- 当
left < right时，搜索范围至少包含两个版本，需要继续收缩。 - 当
left == right时，搜索范围仅剩一个版本，这个版本必然是“第一个错误版本”（因为范围收缩过程中已排除所有不可能的选项），循环终止。
- 当
范围收缩的细节
在循环中，通过 isBadVersion(mid) 的结果调整 left 或 right，确保每次收缩都严格包含目标位置：
-
若
isBadVersion(mid) == true：
mid是错误版本，说明“第一个错误版本”可能是mid或在mid左侧（因为左侧可能有更早的错误版本）。因此收缩右边界：right = mid。 -
若
isBadVersion(mid) == false：
mid是正确版本，说明“第一个错误版本”必然在mid右侧（因为mid及左侧都是正确的）。因此收缩左边界：left = mid + 1。
为什么必然相遇在目标位置？
假设目标位置为 ans（第一个错误版本），证明过程如下：
- 初始范围：
left = 1，right = n，显然ans在[left, right]内。 - 每次收缩后：
- 若
mid是错误版本（mid >= ans），则right = mid，新范围[left, right]仍包含ans（因为ans <= mid = right）。 - 若
mid是正确版本（mid < ans），则left = mid + 1，新范围[left, right]仍包含ans（因为ans > mid = left - 1）。
- 若
- 范围大小的变化：
每次循环后，范围[left, right]的大小严格减小（至少减少 1），因此最终会收缩到left == right。 - 终止时的位置：
由于每次收缩都包含ans，最终left == right时，这个位置必然是ans。
实例验证
以 n = 5，第一个错误版本 ans = 4 为例：
| 步骤 | left | right | mid = left + (right-left)/2 | isBadVersion(mid) | 调整后范围 |
|---|---|---|---|---|---|
| 1 | 1 | 5 | 3 | false（正确版本） | left = 4，范围 [4,5] |
| 2 | 4 | 5 | 4 | true（错误版本） | right = 4，范围 [4,4] |
| 3 | 4 | 4 | 循环终止（left == right） | - | 结果为 4 |
可见，最终 left 和 right 相遇在 4，即目标位置。
总结
while (left < right) 的循环设计通过单调收缩范围，确保每次调整都不遗漏目标位置，最终让 left 和 right 必然相遇在“第一个错误版本”。这种逻辑适用于所有有序且存在唯一解的二分查找问题，是二分查找的经典应用。
和torch.max()区别)
