# [81. Search in Rotated Sorted Array II](https://leetcode.com/problems/search-in-rotated-sorted-array-ii/)
# 思路
在一个经过了循环移位的有序数组（可能有重复元素）里进行查找，在有序数组里进行查找，肯定二分。               
这题和[33. Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array/)其实是类似的，唯一不同就是此题可能有重复元素。
但是基本思路不变，参考[33题题解思路二](https://github.com/ShusenTang/LeetCode/blob/master/solutions/33.%20Search%20in%20Rotated%20Sorted%20Array.md)，
我们得到一个重要的想法：**二分后左右两半至少有一半是有序的**。所以我们可以判断target是否在这有序的一半，若在则丢弃掉另一半进入下一次循环，若不在则丢弃掉有序的这一半进入下一次循环。
那么如何判断哪一半是有序的呢?分为以下几种情况：      
1. 若`nums[mid] == target`，则返回true即可。
2. 若`nums[low] < nums[mid]`，则左半边一定有序；
3. 若`nums[low] > nums[mid]`，则右半边一定有序；
4. 否则，我们无法判断到底哪一边有序，但是可以肯定的是`nums[low] != target`，所以此时我们直接`low++`然后进入下一循环。

最坏的情况就是数组中元素全相等且不等于target，此时时间复杂度为O(n)    
空间复杂度O(1)

# C++
``` C++
class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int mid, low = 0, high = nums.size() - 1;
        while(low <= high){
            mid = (high - low) / 2 + low;
            if(nums[mid] == target) return true;
            if(nums[low] < nums[mid]){
                if(nums[low] <= target && target <= nums[mid]) high = mid - 1;
                else low = mid + 1;
            }
            else if(nums[low] > nums[mid]) {
                if(nums[mid] <= target && target <= nums[high]) low = mid + 1;
                else high = mid - 1;
            }
            else low++;
        }
        return false;
    }
};
```