LeetCode 33 搜索旋轉排序數組：二分查找進階技巧

題目描述

升序數組在未知樞紐處旋轉（如 [4,5,6,7,0,1,2]）。在 O(log n) 時間內搜索目標值，返回索引或 -1。數組無重複元素。

二分判斷邏輯

關鍵觀察：旋轉數組中，任意 mid 將數組分為兩段，**至少有一段是有序的**。

• 若 nums[mid] < nums[r]，右半段 [mid, r] 有序。判斷 target 是否在該區間，縮小範圍。
• 否則左半段 [l, mid] 有序。同理判斷。

標準實現

int search(vector<int>& nums, int target) {
    int l = 0, r = nums.size() - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] < nums[r]) { // 右半段有序
            if (nums[mid] < target && target <= nums[r]) l = mid + 1;
            else r = mid - 1;
        } else { // 左半段有序
            if (nums[l] <= target && target < nums[mid]) r = mid - 1;
            else l = mid + 1;
        }
    }
    return -1;
}

擴展：含重複元素

若允許重複，當 nums[mid] == nums[r] 時無法判斷哪段有序，需 r-- 縮小範圍，最壞情況退化為 O(n)。