題目說明

278.First Bad Version
你是一個產品經理，負責檢查版本是否有 bug。假設你有 n 個版本 [1, 2, ..., n]，某個版本開始之後的版本全都是bad version。

有一個 API 函式 isBadVersion(version) 可以用來判斷某個版本是否壞掉。
請你實作一個函式，找出第一個壞掉的版本。

範例

Input: n = 5, bad = 4
Output: 4
解釋：
isBadVersion(3) → false
isBadVersion(4) → true
所以第一個壞掉的是 4

程式碼（二分搜尋）

Python 解法

（已經內建 isBadVersion API）
def firstBadVersion(n):
left, right = 1, n
while left < right:
mid = (left + right) // 2
if isBadVersion(mid):
right = mid
else:
left = mid + 1
return left

Java 解法

public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left = 1, right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
複雜度分析

• 時間複雜度：O(log n)，用二分搜尋來縮小範圍。
• 空間複雜度：O(1)，只用常數額外變數。

** Java vs Python 差異**

• Python 用 // 取整數除法，Java 直接 /會自動取整數。
• Java 要 extends VersionControl，因為 isBadVersion API 是父類別提供的；Python 則是假設 API 已經存在。
• 兩個的核心邏輯都是用二分搜尋找到第一個 true。