81.Search in Rotated Sorted Array II

给定一个数组，数组是升序排列的，然后现在被循环右移了 n 个单位长度（n未知），且：数组中的元素可重复。给定一个target，求给定的数是否存在于数组中。

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

思路：
此题跟第33题Search in Rotated Sorted Array 很相似，但区别在于，此题元素可重复，同样和33题一样，采用二分查找。
难点：
对于[1,1,1,3,1]和[1,3,1,1,1]，target = 3时，对于nums[mid] = 1, 其 nums[left] = nums[right] = 1，而3既可以在mid左边，又可以在mid右边。所以，对于这种时候，算法就失灵了。解决办法就是这个时候就转为普通的遍历。将nums[mid]与nums[right]比较，当相等时，right--；当nums[mid] > nums[right]时，说明左边是有序的，此时判断target是否属于有序的这一边；当nums[mid] < nums[right]时，说明右边是有序的，此时判断target是否属于有序的这一边。

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int n = nums.size(), left = 0, right = n - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) return true;
            if (nums[mid] < nums[right]) {//右边是有序的
                if (nums[mid] < target && nums[right] >= target) left = mid + 1;
                else right = mid - 1;
            }
            else if (nums[mid] > nums[right]) {//左边是有序的
                if (nums[mid] > target && nums[left] <= target) right = mid - 1;
                else left = mid + 1;
            }
            else right--;//相等时转为普通的遍历
        }
        return false;
    }
};