LeetCode Search in Rotated Sorted Array：旋轉有序數組二分查找完全攻略

題目回顧

嚴格升序數組旋轉若干位（如 [0,1,2,3,4,5] 旋轉 3 位 → [3,4,5,0,1,2]）。在旋轉後數組中查找 target，存在返回下標，否則 -1。要求 O(log n)。

核心觀察：兩段有序

旋轉數組可視為兩段升序數組拼接：[左段][右段]，其中左段所有元素 > 右段所有元素。中點 mid 必屬於左段或右段之一。

二分查找分類討論

class Solution {
public:
    int search(vector& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            
            // 判斷 mid 在左段還是右段
            if (nums[mid] >= nums[left]) { // mid 在左段（含 mid==left）
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1; // target 在左段有序部分
                } else {
                    left = mid + 1;  // target 在右段
                }
            } else { // mid 在右段
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;  // target 在右段有序部分
                } else {
                    right = mid - 1; // target 在左段
                }
            }
        }
        return -1;
    }
};

關鍵邏輯圖解

旋轉數組結構：
[ 左段（大值） ][ 右段（小值） ]
如：[4,5,6,7,0,1,2]
     ↑         ↑   ↑
    left      mid right

mid 在左段 (nums[mid] >= nums[left])：
  - 左段 [left, mid] 有序
  - 若 target 在 [nums[left], nums[mid]) → 縮小到左段
  - 否則 → target 在右段

mid 在右段 (nums[mid] < nums[left])：
  - 右段 [mid, right] 有序
  - 若 target 在 (nums[mid], nums[right]] → 縮小到右段
  - 否則 → target 在左段

邊界情況處理

• 兩個元素：[3,1]，mid=0，nums[mid]=3 >= nums[left]=3，屬左段邏輯正常
• 未旋轉：退化為普通二分，nums[mid] >= nums[left] 恆成立
• 重複值？：題目保證無重複，若有重複需特殊處理（LeetCode 81）

Python 版本

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[mid] >= nums[left]:  # 左段有序
                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

測試用例

assert Solution().search([4,5,6,7,0,1,2], 4) == 0
assert Solution().search([4,5,6,7,0,1,2], 7) == 3
assert Solution().search([4,5,6,7,0,1,2], 0) == 4
assert Solution().search([4,5,6,7,0,1,2], 2) == 6
assert Solution().search([3,1], 3) == 0
assert Solution().search([3,1], 1) == 1
assert Solution().search([1], 0) == -1

總結

旋轉數組二分的核心是：判斷 mid 所在段落，利用該段有序性決定 target 方向。掌握這一模式，同類問題（找最小值、找範圍等）皆可迎刃而解。