題目連結: 33. Search in Rotated Sorted Array

題目描述:一個升序排列的陣列 nums（元素唯一）在某個未知點被旋轉了。例如 [0,1,2,4,5,6,7] 可能變
為 [4,5,6,7,0,1,2]。現在給你一個目標值 target，如果 target 存在於陣列中，返回其索引；否則，返回
-1。
注意:此題要求時間複雜度必須是 O(log n)。

Python

解題思路:

我們取了中點 mid 之後，我們無法像在普通排序陣列中那樣，簡單地透過比較 nums[mid] 和 target 來決定該

往左還是往右。

我們以 mid 為分界，陣列 [left...right] 被分為 [left...mid] 和 [mid...right] 兩部分。由於旋轉點只

有一個，這兩部分中必定有一部分是完整有序的。

一旦確定了哪一半是有序的，我們就檢查 target 是否落在了那個有序的區間內。

• 如果是，我們就在那個有序區間內繼續搜尋。

• 如果不是，那我們就去另一邊（無序的那一半）搜尋。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)-1
        while left <= right:
            mid = (left + right)//2
            if nums[mid] == target:
                return mid
            else:
                if nums[left] <= nums[mid]:
                    if nums[left] <= target and target < nums[mid]:
                        right = mid - 1
                    else:
                        left = mid + 1 
                else:
                    if nums[mid] < target and target <= nums[right]:
                        left = mid + 1 
                    else:
                        right = mid - 1
        return -1

演算法分析:

• if nums[left] <= nums[mid]:先判斷中間點有沒有在左區間。
• if nums[left] <= target and target < nums[mid]:檢查 target 是否落在這個有序區間內，如果True，縮小右邊界，否則縮小左邊界。
• if nums[mid] < target and target <= nums[right]:檢查 target是否落在這個有序右半邊內，如果True，縮小左邊界。
• 最後就找到了target。

複雜度分析:

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

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