33. 搜索旋转排序数组

难度：🟡 Medium | 标签：二分查找 | 状态：⬜ LeetCode 链接

思路

判断 mid 在哪一半有序，再判 target 是否在该半。

• nums[l] <= nums[m] → 左半有序
• 否则右半有序

代码

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

复杂度

• 时间 O(log n)，空间 O(1)

易错 / 回顾

• nums[l] <= nums[m] 含等号（处理 l == m 的边界）
• 内部区间判断用闭区间 <= target && target <，写错位 WA
• 含重复值版本（81）要处理 nums[l] == nums[m] 的退化