81. Search in Rotated Sorted Array II

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

 

Example 1:

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

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

Constraints:

1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums is guaranteed to be rotated at some pivot.
-104 <= target <= 104
 

Follow up: This problem is the same as Search in Rotated Sorted Array, where nums may contain duplicates. Would this affect the runtime complexity? How and why?

这种带有排过序性质的数组，寻找某元素，基本都是使用二分法。

将一个排过序的数组，在某个元素处进行旋转后进行查找。首先可以用二分法，我们找到了中间值之后，我们必须得判断想要的元素在左边还是右边。

在排过序的数组中很简单的就能知道了，然而在旋转过的数组中就不太好判断了。

假设数组的元素都不一样，那么当中间元素大于目前右范围内的最后一个元素的时候，那么右范围的子数组必定是有序的。因为假设中间值落在经过旋转的范围内，那么该范围的值肯定是大于右边所有值的。

然而有重复数字就不好说了，遇到相等的值就无法进行判断了。这里其实只要遇到中间值和右范围内最大数相等的情况，只要将右指针往前挪动一下即可。因为首先中间值肯定和target进行比较过，肯定不等于target的情况下，我们只要将查找的范围进行缩小，将和中间值相等的元素剔除出去即可。

class SearchInRotatedSotedArrayII : public Solution {
public:
    void Exec() {
    }
    bool search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return true;
            if (nums[mid] < nums[right]) {
                if (target >= nums[mid] && target <= nums[right]) left = mid + 1;
                else right = mid - 1;
            } else if (nums[mid] > nums[right]) {
                if (target >= nums[left] && target <= nums[mid]) right = mid - 1;
                else left = mid + 1;
            } else right--;
        }
        return false;
    }
};