題目出處
難度
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，
概念要剛好相反。