LeetCode Search Insert Position：旋轉有序數組的二分查找

問題描述

在一個可能經過旋轉的升序數組中查找目標值，返回索引，不存在返回 -1。數組無重複元素。例如 [4,5,6,0,1,2] 是 [0,1,2,4,5,6] 旋轉後的結果。

核心觀察

旋轉數組具有局部有序性：以中點 mid 分割，至少一側是完全有序的。利用這一性質可判斷目標值落在哪一側。

二分判斷邏輯

• 若 A[mid] == target，直接返回
• 若 A[left] <= A[mid]：左半段有序
  • 若 A[left] <= target < A[mid]，目標在左側，right = mid - 1
  • 否則在右側，left = mid + 1
• 否則右半段有序
  • 若 A[mid] < target <= A[right]，目標在右側，left = mid + 1
  • 否則在左側，right = mid - 1

完整代碼

class Solution {
public:
    int search(vector<int>& 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;
            if (nums[left] <= nums[mid]) { // 左半段有序
                if (nums[left] <= target && target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            } else { // 右半段有序
                if (nums[mid] < target && target <= nums[right])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }
        return -1;
    }
};

複雜度

• 時間：O(log N)
• 空間：O(1)

易錯點提醒

1. 邊界條件：left <= right 而非 <
2. 判斷有序段時用 <= 而非 <，因為可能 left == mid
3. 目標值比較嚴格區分 < 和 <=，避免死循環

這道題是「旋轉數組二分」的入門經典，掌握「判斷哪側有序 → 目標是否在有序段」的雙重判斷模板，可解決同類變種問題。