LeetCode 筆記 - 278-First-Bad-Version

Posted on 標籤
面對尋找第一個損壞版本的問題，本文展示二元搜尋（Binary Search）的經典應用。透過不斷折半縮小搜尋範圍，能以對數級時間複雜度快速鎖定故障點，是開發者在處理有序範圍搜尋問題時的必備演算法知識。
⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

題目在此 278. First Bad Version

給正整數 n，找出 1 ~ n 第一個壞掉的版本

解題思維

利用 Binary Search 來快速搜尋就可以了

完成✅

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        
        if n == 1:
            return 1
        
        start = 0
        end = n
        
        while start <= end:
            mid = int((start + end) / 2)
            
            if isBadVersion(mid):
                end = mid - 1
            elif isBadVersion(mid + 1):
                return mid + 1
            else:
                start = mid + 1
        
        return -1

也許你也會想看看