[LeetCode解題攻略] 33. Search in Rotated Sorted Array

問題描述

給定一個按照升序排序的整數數組，但該數組可能在某個未知的軸點旋轉（例如，nums = [4,5,6,7,0,1,2]）。請你在數組中搜索目標值 target，如果找到則返回其索引，否則返回 -1。

限制條件

• 時間複雜度應為 O(log n)。
• 你可以假設數組中不存在重複元素。
• 所有數值均在整數範圍內。

範例1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

範例2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

範例3:

Input: nums = [1], target = 0
Output: -1

解法一：改進的二分搜索

思路

由於數組經過旋轉，因此分為兩個有序區間。在進行二分搜索時，可以根據中點位置的數值和邊界條件來確定目標值所屬的區間，從而縮小搜索範圍。

步驟

1. 初始化兩個指針 left 和 right，分別指向數組的起點和終點。
2. 計算中點索引 mid = (left + right) // 2。
3. 如果中點值等於目標值，直接返回索引。
4. 如果左半部分有序（即 nums[left] <= nums[mid]），判斷目標值是否落在此範圍：
5. • 若是，將 right 移動到 mid - 1；
   • 否則，將 left 移動到 mid + 1。
5. 如果右半部分有序，類似判斷目標值是否落在此範圍：
6. • 若是，將 left 移動到 mid + 1；
   • 否則，將 right 移動到 mid - 1。
6. 如果遍歷結束仍未找到目標值，返回 -1。

程式碼

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            # 判斷左半部分是否有序
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:  # 右半部分有序
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1

時間複雜度

• 時間複雜度：O(log n)，二分法的特性使得每次操作將搜索範圍縮小一半。
• 空間複雜度：O(1)，只使用常數額外空間。

解法二：遞歸二分搜索

思路

這是一個遞歸版本的二分搜索，邏輯與迭代法相同。根據旋轉後的特性，選擇遞歸左或右子區間。

程式碼

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def binary_search(left, right):
            if left > right:
                return -1
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            if nums[left] <= nums[mid]:  # 左半部分有序
                if nums[left] <= target < nums[mid]:
                    return binary_search(left, mid - 1)
                else:
                    return binary_search(mid + 1, right)
            else:  # 右半部分有序
                if nums[mid] < target <= nums[right]:
                    return binary_search(mid + 1, right)
                else:
                    return binary_search(left, mid - 1)
        
        return binary_search(0, len(nums) - 1)

時間複雜度

• 時間複雜度：O(log n)，與迭代法相同。
• 空間複雜度：O(log n)，遞歸深度與二分次數相同。

解法三：線性搜索

思路

如果時間複雜度要求可以放寬，則可以通過遍歷數組進行查找。這是最簡單的方法，也是最花時間的方法。

程式碼

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        for i in range(len(nums)):
            if nums[i] == target:
                return i
        return -1

時間複雜度

• 時間複雜度：O(n)，最差情況需遍歷整個數組。
• 空間複雜度：O(1)。

結論

• 如果需要滿足 O(log n) 的時間複雜度，建議使用解法一（迭代法）或解法二（遞歸法）。
• 若問題條件放寬，可使用解法三進行線性搜索。