問題 I：無重複元素

有序數組旋轉後（如 [4,5,6,7,0,1,2]），搜索目標值，返回索引或 -1。要求 O(log n)。

核心觀察：二分查找 + 區間有序性判斷

中間值 mid 將數組分為兩半，**至少一半是有序的**：

• 若 nums[mid] < nums[tail]：右半部 [mid, tail] 有序
• 若 nums[mid] > nums[head]：左半部 [head, mid] 有序

判斷目標值在有序半部內 → 普通二分；否則去無序半部繼續特殊二分。

代碼實現（I）

class Solution {
public:
    int search(vector& nums, int target) {
        int n = nums.size();
        int head = 0, tail = n - 1;
        while (head <= tail) {
            if (nums[head] == target) return head;
            if (nums[tail] == target) return tail;
            int mid = (head + tail) / 2;
            if (nums[mid] == target) return mid;

            if (nums[mid] < nums[head]) { // 右半部有序
                if (nums[mid] < target && target < nums[tail])
                    head = mid + 1;
                else
                    tail = mid - 1;
            } else if (nums[mid] > nums[tail]) { // 左半部有序
                if (nums[head] < target && target < nums[mid])
                    tail = mid - 1;
                else
                    head = mid + 1;
            } else { // 完全有序（未旋轉或旋轉 n 次）
                if (target < nums[mid]) tail = mid - 1;
                else head = mid + 1;
            }
        }
        return -1;
    }
};

關鍵細節：每次移動一位

head = mid + 1, tail = mid - 1 保證區間縮小，避免死循環。循環前單獨檢查 head/tail/mid 可減少分支。

問題 II：允許重複元素

重複導致無法判斷哪半部有序（如 [1,2,1,1]，mid=1, head=1, tail=1）。解決：**跳過重複元素**縮小邊界，退化為問題 I。

代碼實現（II）

class Solution {
public:
    bool search(vector& nums, int target) {
        int n = nums.size();
        int head = 0, tail = n - 1;
        while (head <= tail) {
            if (nums[head] == target) return true;
            if (nums[tail] == target) return true;
            int mid = (head + tail) / 2;
            if (nums[mid] == target) return true;

            // 跳過 head 端重複元素
            if (nums[mid] == nums[head]) {
                int i = head;
                while (i <= mid && nums[i] == nums[mid]) i++;
                head = i;
            }
            // 跳過 tail 端重複元素
            if (nums[mid] == nums[tail]) {
                int i = tail;
                while (i >= mid && nums[i] == nums[mid]) i--;
                tail = i;
            }
            if (head > tail) break; // 全部跳過完畢

            if (nums[mid] < nums[head]) { // 右半部有序
                if (nums[mid] < target && target < nums[tail]) head = mid + 1;
                else tail = mid - 1;
            } else if (nums[mid] > nums[tail]) { // 左半部有序
                if (nums[head] < target && target < nums[mid]) tail = mid - 1;
                else head = mid + 1;
            } else { // 有序
                if (target < nums[mid]) tail = mid - 1;
                else head = mid + 1;
            }
        }
        return false;
    }
};

複雜度分析

• 問題 I：O(log n) 時間，O(1) 空間
• 問題 II：最壞 O(n)（全等元素需線性掃描），平均 O(log n)

關鍵區別總結