题目内容

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

示例

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true
示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

提示

1、1 <= nums.length <= 5000
2、-10^4 <= nums[i] <= 10^4
3、题目数据保证 nums 在预先未知的某个下标上进行了旋转
4、-10^4 <= target <= 10^4

题解

本题考查二分算法。在与之前类似的搜索旋转排序数组 I 不同的是，这里允许出现重复数字，这样就导致被旋转后的数组的前端开头与后段结尾可能存在相同的数字，我们无法通过x >= nums[0]来进行二分处理。

为了能够进行二分，我们需要对数组做出一些变动，即当前段开头部分数字和后端末尾数字一致时，把前端开头部分相同的数字去掉或者把后端末尾部分相同的数字去掉，使其达到二分条件后再进行二分处理。由于相同数字仅去掉了一部分，因此不影响答案中需要寻找目标值，也就不影响答案的正确性。

代码

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        //近似二分优化。即二分之后，将某一部分的重复元素删除掉之后，保证可以二分就好，然后判断是否存在target
        if(nums.empty()) return false;
        int R = nums.size() - 1;//定义一个终点
        while(R >= 0 && nums[R] == nums[0]) R--;//当终点大于等于0 且nums[R]等于开头的话，将该数删掉，也就是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;
        }
        //确定好部分后，确定一下左右区间，然后继续进行二分操作
        if(target >= nums[0]) r = l, 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;
    }
};