題目出處
153. Find Minimum in Rotated Sorted Array
難度
medium
題目分類
Array, Binary Search
2026-08-28 三刷
個人範例程式碼 - 三刷 (2026/08/28)
class Solution:
def findMin(self, nums: List[int]) -> int:
left = 0
right = len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] < nums[right]: # right asc, min in left
right = mid
else: # left asc, min in right
left = mid + 1 # except mid, ex: [2, 1]
return nums[left]
算法說明
經典的 binary search, 這題需要特別留意邊界處理
幾個重點
- 判「右側」有序？ 通常最小會出現在旋轉一側
例外處理：雙邊皆有序 （從頭到尾都有序），判準都是判右側，因為右側有序，也會去左側找最小 （依照小 -> 大） - 處理最後的邊界， left = mid + 1
如果不移動，最後會導致無限迴圈 （left 原地不動）
且為什麼可以這樣移動？因為 mid 在判右側有序時已經看過，如果右側無序，mid 自然也不可能是最小
Time Complexity
O(logN)
Space Complexity
O(1)
Boundary conditions
- [1] -> while left < right
- [1, 2]
- [2, 1] -> left = mid + 1
2026-07-24 二刷
個人範例程式碼 - 二刷 (2026/07/24)
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2 # left <= mid < right
if nums[mid] < nums[right]: # ans in left side
right = mid # mid can be ans (rotation start here)
else: # ans in right side
left = mid + 1
return nums[left]
算法說明
第一次寫的時候我在 nums[mid] < nums[right] 中加了 early return (提前判 asc 而提早回傳答案)，
這解法合理但容易讓邏輯不夠乾淨，且 early return 省下的量級不多，還多一層判斷。
可以記憶 left < right 配 right = mid (處理 mid 為答案的情況)
Time Complexity
O(logN)
Space Complexity
O(1)
Boundary conditions
- [1]：直接出迴圈
- [1,2]：right = mid 能處理
- [2,1]：left = mid + 1 能處理
- [1,2,3,4]：變 [1,2] 然後同 2.
2022-04-05 一刷
個人範例程式碼 - 一刷 (2022/04/05)
class Solution:
def findMin(self, nums: List[int]) -> int:
if not nums:
return 0
start, end = 0, len(nums)-1
while(start + 1 < end):
mid = (start + end) // 2
if nums[mid] == nums[end]: # if special case exist
start = mid
elif nums[mid] > nums[end]: # still going up
start = mid
else: # [mid] < [end] # going down, move start yo get closer
end = mid
else:
if(nums[start] <= nums[end]):
return nums[start]
else:
return nums[end]
算法說明
binary search
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
input handling
處理沒有輸入的時候，return 0
Boundary conditions
正常的 start, end 要注意，此外
注意點 - 要比較的大小對象? First? Last?
請思考以下問題：
我們的 nums[mid] 應該要比較誰?
(A) > nums[first]
(B) >= nums[first]
(C) > nums[end]
(D) >= nums[end]
思考一下，答案為 (D) >= nums[end]
(B), (C) 基本上代表是同一個意思，而只比較 first 會出問題的地方在於 [2, 3, 1] 與 [1, 2, 3]
正常的 [2, 3, 1]，我們可以透過 2 > 1 處理掉，start 往中間移動，
但 [1, 2, 3]，我們會發現我們移動了 1 -> 2，start 被移動掉了，因此找不到正確答案。
而 (A) > nums[first]，就更不用提了。