搜索旋转排序数组 II 图解题解

数组被旋转过又带重复，只判 target 在不在

nums 本是升序，从某处切开对调，比如 [0,1,1,1] 变 [1,1,1,0]，还可能有重复数字。给定 target，在就返回 true、否则 false，只判在不在。题面 nums=[1,1,1,0,1]、target=0 为 true。

扫一遍能过，可为什么不甘心停在 O(n)

把 target 和每个数挨个比，n 个数最坏比满 n 次，是 O(n)。数据小也能过，但数组是升序旋转来的、自带秩序没用上；升序本可二分 O(log n) 定位，题目旋转又掺重复，就是逼你捡回二分。

凭什么还能二分，重复又是怎么搅局的

旋转后数组不再整体有序，却是两段各自升序的拼接。以中点 mid 为界，nums[l]≤nums[mid] 就说明左半升序，否则拐点在左半、右半才升序；锁定有序那半看 target 在不在它的范围里，在就进这半、不在去另一半，一样砍掉一半。

麻烦全在重复：nums[l]=nums[mid] 时左半可能有序也可能不是，光看分不清；尤其三者全相等，大小比较彻底失去区分力，哪半有序都判不了。

三个数一样时，指针到底该往哪挪

每轮取中点 mid=(l+r)//2，nums[mid]==target 就返回 true。没中分三支：三者 nums[l]、nums[mid]、nums[r] 相等时判不出哪半有序，只能 l 加一、r 减一各缩一格，最坏退化就埋在这；nums[l]≤nums[mid] 时左半有序，nums[l]≤target<nums[mid] 收左 r=mid-1、否则 l=mid+1；否则右半有序，nums[mid]<target≤nums[r] 收右 l=mid+1、否则 r=mid-1。开闭对齐有序方向，写反等号就把 target 推错半边。

拿 [1,1,1,0,1] 找 0，三轮各发生什么

起手 l=0、r=4。第一轮 mid=(0+4)//2=2，nums[2]=1 不是 0；nums[0]、nums[2]、nums[4] 全是 1，三者相等，各缩一格，l 到 1、r 到 3。

第二轮 l=1、r=3，mid=2，nums[2]=1 不是 0；nums[l]=nums[mid]=1 但 nums[r]=nums[3]=0，不触发三者相等，nums[l]≤nums[mid] 判左半有序，1≤0<1 不成立故 target 靠右，l=mid+1=3。第三轮 l=r=3，mid=3，nums[3]=0 命中返回 true。首轮靠缩一格跨过重复区，后两轮才是常规二分。

少了缩一格这一支，重复数组会怎么判错

砍半时是 O(log n)、空间 O(1)；但 [1,1,1,1,1] 找 0 这种几乎全相等的数组，每轮都撞三者相等只能缩一格，退化成 O(n)。

照搬 33 题漏掉 nums[l]==nums[mid]==nums[r] 这支，重复数组哪半有序会判错、区间收不动死循环。相等时只动一边、l++ 忘了 r--，某些分布下区间收不干净会漏看 target，两端得同时缩。开闭的等号也别写反，左半该 <、右半该 ≤，站错边 target 就判到另一半。

Python

def search(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target:        # 命中
            return True
        if nums[l] == nums[mid] == nums[r]:  # 三者相等：缩一格
            l += 1; r -= 1
        elif nums[l] <= nums[mid]:     # 左半有序
            if nums[l] <= target < nums[mid]:
                r = mid - 1
            else:
                l = mid + 1
        else:                          # 右半有序
            if nums[mid] < target <= nums[r]:
                l = mid + 1
            else:
                r = mid - 1
    return False

C++

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

Java

public boolean search(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (nums[mid] == target) return true;
        if (nums[l]==nums[mid] && nums[mid]==nums[r]) { l++; r--; }
        else if (nums[l] <= nums[mid]) {        // 左半有序
            if (nums[l] <= target && target < nums[mid]) r = mid - 1;
            else l = mid + 1;
        } else {                                 // 右半有序
            if (nums[mid] < target && target <= nums[r]) l = mid + 1;
            else r = mid - 1;
        }
    }
    return false;
}