LeetCode 278: First Bad Version

問題描述

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. 最直覺且基礎的解法，從版本 1 依序迭代至版本 n 並逐一檢查，若 isBadVersion 回傳 True，則立刻回傳當前版本。

程式碼

def first_bad_version(n: int) -> int:
    for version in range(1, n + 1):
        if isBadVersion(version):
            return version

複雜度分析

• 時間複雜度：O(N)， 其中 N 為 n。
• 空間複雜度：O(1)

解法二：二元搜尋法

解題思路

根據題目要求，我們需要在一段範圍 ([1, 2, ..., n] ) 內找到特定目標，且在陣列中的元素是有序的。這給予了我們足夠多的提示可以使用二元搜尋法。在每次的搜尋過程中不斷縮小搜尋範圍，進一步逼近我們要搜尋的目標。

步驟詳解

1. 使用兩個指針 left 及 right 來代表當前搜尋範圍的左右界線。
2. 當 left 小於或等於 right 時：
   1. 計算當前範圍的中心點 mid (left + right // 2)。
   2. 檢查 mid 指向的版本，若為正常版本 (isBadVersion(mid) == False)，代表在 mid 之前的所有版本都也會是正常版本，且可以全部跳過。將 left 指針移至 mid 的後一個元素。
   3. 若 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

複雜度分析

• 時間複雜度：O(logN)， 其中 N 為 n。
• 空間複雜度：O(1)

參考資料

• LeetCode 原題出處：First Bad Version – LeetCode