問題描述
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n
versions [1, 2, ..., n]
and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version)
which returns whether version
is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
限制條件
1 <= bad <= n <= 231 - 1
範例
- Example 1:
Input:n = 5, bad = 4
Output:4
Explanation:call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version. - Example 2:
Input:n = 1, bad = 1
Output:1
解法一:暴力解
步驟詳解
- 最直覺且基礎的解法,從版本
1
依序迭代至版本n
並逐一檢查,若isBadVersion
回傳True
,則立刻回傳當前版本。
程式碼
def first_bad_version(n: int) -> int:
for version in range(1, n + 1):
if isBadVersion(version):
return version
Python複雜度分析
- 時間複雜度:
O(N),
其中 N 為n
。 - 空間複雜度:
O(1)
解法二:二元搜尋法
解題思路
根據題目要求,我們需要在一段範圍 ([1, 2, ..., n]
) 內找到特定目標,且在陣列中的元素是有序的。這給予了我們足夠多的提示可以使用二元搜尋法。在每次的搜尋過程中不斷縮小搜尋範圍,進一步逼近我們要搜尋的目標。
步驟詳解
- 使用兩個指針
left
及right
來代表當前搜尋範圍的左右界線。 - 當
left
小於或等於right
時:- 計算當前範圍的中心點
mid
(left + right // 2
)。 - 檢查
mid
指向的版本,若為正常版本 (isBadVersion(mid) == False
),代表在mid
之前的所有版本都也會是正常版本,且可以全部跳過。將left
指針移至mid
的後一個元素。 - 若 mid 指向的是有問題的版本 (
isBadVersion(mid) == True
),要特別注意的是由於我們這邊要找的是第一個有問題的版本,因此mid
並不見得就是我們要的答案。在這個情況下,我們還要檢查mid
的前一個版本 (mid - 1
) 是否也是有問題的版本。若是,代表mid
並不是我們要找的答案,將right
指針移至mid
的前一個元素並重複上列步驟。反之,若mid
的前一個版本是正常的版本,這意味著mid
就是第一個發生問題的版本,直接回傳mid
即可。
- 計算當前範圍的中心點
程式碼
def first_bad_version(self, n: int) -> int:
left = 1
right = n
while left <= right:
mid = (left + right) // 2
if not isBadVersion(mid):
left = mid + 1
else:
if mid > 1 and isBadVersion(mid - 1):
right = mid - 1
else:
return mid
Python複雜度分析
- 時間複雜度:
O(logN),
其中 N 為n
。 - 空間複雜度:
O(1)
參考資料
- LeetCode 原題出處:First Bad Version – LeetCode