分析

• 本题的考点：二分。

• 本题是Leetcode 0033 搜索旋转排序数组的扩展题目，区别只有一点：本题中可以存在相同元素。

• 为了能二分出分界点，我们需要删除最后和nums[0]相等的数据，这样就转换成了Leetcode 0033 搜索旋转排序数组，按照LC33的做法做一遍即可，分析如下：

• 使用两次二分：（1）二分出旋转点的位置；（2）第二次二分出答案。关键是第一次二分，如下图：

• 我们可以发现左右两部分具有两段性，左边元素全部$\ge nums[0]$，右边的元素$<nums[0]$。据此可以二分出分界点。

• 之后判断我们需要寻找的目标值target和nums[0]之间的关系，如果$target \ge nums[0]$，则在第一段中第二次二分，否则在另一半二分。

代码

• C++

class Solution {
public:
    bool search(vector<int> &nums, int target) {

        int R = nums.size() - 1;
        while (R >= 0 && nums[R] == nums[0]) R--;
        if (R < 0) return nums[0] == target;  // 说明所有的数都一样

        int l = 0, r = R;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] >= nums[0]) l = mid;
            else r = mid - 1;
        }

        // 寻找target在哪一有序区间中
        if (target >= nums[0]) l = 0;
        else l++, r = R;

        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }

        return nums[r] == target;
    }
};

• Java

class Solution {
    public boolean search(int[] nums, int target) {

        int R = nums.length - 1;
        while (R >= 0 && nums[R] == nums[0]) R--;
        if (R < 0) return nums[0] == target;  // 说明所有的数都一样

        int l = 0, r = R;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] >= nums[0]) l = mid;
            else r = mid - 1;
        }

        // 寻找target在哪一有序区间中
        if (target >= nums[0]) l = 0;
        else {
            l++; r = R;
        }

        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }

        return nums[r] == target;
    }
}

时空复杂度分析

• 时间复杂度：$O(n)$，n为数组长度。因为当数组中所有元素都相同时，需要遍历一遍数数组。

• 空间复杂度：$O(1)$。