題目出處
153. Find Minimum in Rotated Sorted Array
難度
medium
個人範例程式碼
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]，就更不用提了。