假设按照升序排序的数组在预先未知的某个点上进行了旋转。

    ( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

    编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 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. class Solution {
    2. public:
    3.     // 由于旋转的排序数组存在重复的数值，无法判断哪一部分有序；
    4.     // 所以：需要在每一步二分搜索之前有一个判断的过程，判断哪一部分有序。
    5.     // 或则：在每一步二分之前对[left, right]之间的数据进行首尾去重
    6.     bool search(vector<int>& nums, int target) {
    7.         int n = nums.size();
    8.         if (0 == n) return false;
    9.         if (1 == n) return target == nums[0] ? true : false;
    10.         int left = 0, right = n-1;
    11.         // 二分搜索
    12.         while(left <= right){
    13.             // ================= Method1 =====================
    15.             // [left, right]子区间做一个首尾去重
    16.             while(left != right && nums[left] == nums[right])
    17.                 left++;
    18.             int mid = (left + right) >> 1;
    19.             if (nums[mid] == target)
    20.                 return true;
    22.             // ===================Method2=======================
    23.             /*
    24.             int mid = (left + right) >> 1;
    25.             if (nums[mid] == target)
    26.                 return true;
    27.             // 区分出哪一部分有序
    28.             if (nums[left] == nums[mid]){
    29.                 ++left;
    30.                 continue;
    31.             }
    32.             */
    33.             // ================================================
    35.             if (nums[left] <= nums[mid]){
    36.                 if (nums[left] <= target && target < nums[mid])
    37.                     right = mid-1;
    38.                 else
    39.                     left = mid+1;
    40.             }
    41.             else{
    42.                 if(nums[mid]<target && target<=nums[right])
    43.                     left = mid+1;
    44.                 else
    45.                     right = mid-1;
    46.             }
    47.         }
    48.         return false;
    49.     }
    50. };