LeetCode 278. 第一個錯誤的版本 解析

這個問題要求找到第一個錯誤的版本，其中給定一個 API isBadVersion(version) 可以判斷某個版本是否錯誤。由于版本號是有序的，且錯誤版本之后的所有版本都是錯誤的，因此可以使用二分查找高效地定位第一個錯誤版本。

方法思路

1. 二分查找框架：
   初始化左右指針 left 和 right 分別指向第一個和最后一個版本。
   在每次循環中，計算中間版本 mid，并調用 isBadVersion(mid) 判斷：

   • 若 mid 是錯誤版本，說明第一個錯誤版本在 mid 或其左側，更新 right = mid。
   • 若 mid 不是錯誤版本，說明第一個錯誤版本在 mid 右側，更新 left = mid + 1。

2. 終止條件：
   當 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 即為第一個錯誤版本}
};

代碼解釋

1. 二分查找初始化：
   left = 1 和 right = n 分別表示版本范圍的左右邊界。

2. 防止整數溢出：
   使用 mid = left + (right - left) / 2 代替 mid = (left + right) / 2，避免當 left 和 right 都很大時發生整數溢出。

3. 循環條件：
   while (left < right) 確保循環在 left 和 right 相遇時終止。

4. 條件判斷：

   • 若 isBadVersion(mid) 為真，說明第一個錯誤版本在 [left, mid] 范圍內，更新 right = mid。
   • 若為假，說明第一個錯誤版本在 [mid+1, right] 范圍內，更新 left = mid + 1。

5. 返回結果：
   循環結束時，left 和 right 指向同一個位置，即第一個錯誤版本。

復雜度分析

• 時間復雜度：O(log n)，每次迭代將搜索范圍縮小一半。
• 空間復雜度：O(1)，只需要常數級額外空間。

示例

假設 n = 5，且第一個錯誤版本是 4。
二分查找過程如下：

1. 初始：left = 1, right = 5, mid = 3
   • isBadVersion(3) 返回 false → left = 4。
2. 第二次迭代：left = 4, right = 5, mid = 4
   • isBadVersion(4) 返回 true → right = 4。
3. 終止條件：left == right == 4，返回 4。

關鍵點

1. 二分查找變體：
   與傳統二分查找不同，這里的 right 指向錯誤版本，因此更新時直接將 right = mid，而非 mid - 1。

2. 防止溢出：
   使用 left + (right - left) / 2 計算中間值，避免整數溢出。

3. 循環終止條件：
   left < right 確保不會陷入死循環，且最終 left 即為所求結果。

這種方法高效且簡潔，是解決有序數組中查找特定元素問題的經典思路。

在二分查找解決“第一個錯誤版本”問題時，while (left < right) 循環的設計是為了精準收縮搜索范圍，最終讓 left 和 right 相遇在目標位置（第一個錯誤版本）。以下從邏輯推導和實例驗證兩方面詳細解釋：

核心邏輯：范圍收縮的必然性

二分查找的本質是通過不斷排除不可能的范圍，最終將搜索范圍縮小到唯一解。在“第一個錯誤版本”問題中：

1. 范圍的單調性：
   題目明確“錯誤版本之后的所有版本都是錯誤的”，即版本序列具有單調性：
   [正確版本, 正確版本, ..., 第一個錯誤版本, 錯誤版本, ..., 錯誤版本]
   這種單調性保證了二分查找的可行性。

2. 循環條件 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（第一個錯誤版本），證明過程如下：

1. 初始范圍：left = 1，right = n，顯然 ans 在 [left, right] 內。
2. 每次收縮后：
   • 若 mid 是錯誤版本（mid >= ans），則 right = mid，新范圍 [left, right] 仍包含 ans（因為 ans <= mid = right）。
   • 若 mid 是正確版本（mid < ans），則 left = mid + 1，新范圍 [left, right] 仍包含 ans（因為 ans > mid = left - 1）。
3. 范圍大小的變化：
   每次循環后，范圍 [left, right] 的大小嚴格減小（至少減少 1），因此最終會收縮到 left == right。
4. 終止時的位置：
   由于每次收縮都包含 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 必然相遇在“第一個錯誤版本”。這種邏輯適用于所有有序且存在唯一解的二分查找問題，是二分查找的經典應用。