LeetCode 33: Search in Rotated Sorted Array ·

基本資料
#

難易度: medium 第一次嘗試：2022-10-21

提交紀錄：Wrong Answer → Accepted → Wrong Answer → Accepted → Wrong Answer → Accepted → Wrong Answer ×4 → Accepted → Wrong Answer ×2 → Accepted → Wrong Answer → Accepted → Runtime Error → Accepted ×4

解題思路
#

切在 mid，左半 [l, mid] 和右半 [mid, r] 至少有一邊是排序好的（Binary Search）：

nums[l] <= nums[mid]：左半有序。目標在 [nums[l], nums[mid]) 之間就往左，否則往右。
否則右半有序。目標在 (nums[mid], nums[r]] 之間就往右，否則往左。

只能用有序的那一半判斷目標在不在裡面。

我的嘗試
#

2022 年第一次 AC 的其實是線性掃描（O(n)）。之後練二分搜尋的 10 幾次 WA 都是方向判斷錯：

一版先用 nums[mid] >= target 決定，再檢查範圍，但用來檢查的那一半不一定有序。例如 [8, 9, 10, 3]、target = 10：答案 2，回傳 -1。
一版只看 nums[r] >= target 就往左縮，方向反了。例如 [1, 5]、target = 5 回傳 -1。

正確解法
#

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