題目連結: 153. Find Minimum in Rotated Sorted Array

題目描述:一個原本升序排列的陣列 nums（元素唯一），在某個未知的點被旋轉了。例如，陣列

[0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2]。請找出並返回這個陣列中的最小元素。

注意:此題要求時間複雜度必須是 O(log n)。

Python

解題思路:
我的想法是nums[mid]與最後一個數字去做比較，如果nums[mid]比陣列的最後一個值還小，真正的最小值可能是

nums[mid] 本身，或者在它的左邊。只有旋轉點右側的值才會比最後一個數小。所以範圍縮至 [left, mid]。

如果nums[mid] 的值大於或等於陣列的最後一個值，nums[mid]肯定不是最小值，而且真正的最小值一定在它的右

邊，所以將範圍縮至 [mid + 1, right]。

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[-1]:
                right = mid 
            else:
                left = mid +1
        return nums[right]

複雜度分析:

• while 迴圈的每一次迭代中，搜索區間 [left, right] 的大小都會被縮減大約一半，時間複雜度為 O(log n)。
• 使用了固定數量的額外變數 (left, right, mid) 來儲存左右兩端和中間值，空間複雜度為 O(1)。

今天就介紹到這邊，有問題都可以留言
下回見!!