題目出處

278. First Bad Version

難度

easy

個人範例程式碼

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        # isBadVersion = true 
        # OOO(X)XXX
        # FFF(T)TTT <- notice this!
        if not n: 
            return 0

        start, end = 1, n

        while(start + 1 < end):
            mid = (start + end) // 2
            if isBadVersion(mid): # [mid] = false (still good version.), move end to search after     
                end = mid
            else: # if isBadVersion(mid) == True: # [mid] = true, move start to search behind
                start = mid

        else:
            if isBadVersion(start):
                return start
            elif isBadVersion(end):
                return end
            else:
                return 0

        return 0

算法說明

變化版本的 binary search，採用的策略為先縮小範圍再得到答案。

也就是說 left, right 縮小至最小範圍的 left, right，再去判斷答案。

• 當然比較常見的方法是：left, right 找 mid，mid 直接找到答案會更為簡潔。

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

input handling

注意 input nums 為 0 的時候的處理，return 個 0 給他 (題目好像沒特別提到這個，我自己加的)

Boundary conditions

start 與 end 的處理一直都是 binary search 常出錯的地方，這邊要細心一些。

我採用網路上看到的 start + 1 < end 的方式，先縮小 left, right 範圍
並且不把目標放在直接找到 mid 做為答案。

再從最小範圍 left, right 中找到最終解答。

其他重點

注意 isBadVersion 是「錯的」回傳「True」，
這個雙重否定有弄到我XD，
概念要剛好相反。

Reference

• 第一个错误的代码版本 · First Bad Version