题目描述

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

题意：一个有序数组，将数组后面一部分元素移到数组最开始的地方，在这个数组中找到某个数是否存在。33题的加强版，允许有重复元素。因为涉及到精确值的查找，我们使用二分查找模板一 。

样例

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

算法1

我们知道，整个旋转后的数组由两个非严格单调递增的子数组组成，假设$[left,right]$是当前搜索空间。

• 如果$nums[mid] > nums[left]$，说明$mid$在第一个非严格单调递增子数组中，那么$[left,mid]$这个区间肯定是非严格单调递增的。那么如果$target$在$[nums[left],nums[mid])$这个区间内，那么搜索范围就会变成$[left,mid-1]$。
• 如果$nums[mid] < nums[left]$，说明$mid$在第二个非严格单调递增子数组中，那么$[mid,right]$这个区间肯定是非严格单调递增的。那么如果$target$在$(nums[mid],nums[right])$这个区间内，那么搜索范围就会变成$[mid+1,right]$。
• 最后一种情况则是最复杂的。如果$nums[mid]=nums[left]$，那么$mid$既有可能在第一个区间内(从$left$到$mid$的数都相等)，也有可能在第二个区间内（从$mid$到$right$的值都相等，且等于$left$）。假设原数组是[1,2,3,3,3,3,3]，那么旋转之后有可能是[3,3,3,3,3,1,2]，或[3,1,2,3,3,3,3]。这个时候，其实我们只需要将$left = left + 1$就可以了，因为$nums[left] = nums[mid],nums[mid] != target$，那么$nums[left]!=target$，所以我们可以将搜索范围缩小。

@yxc说过他想到的二分解法在最坏情况下会退化成$O(n)$的时间复杂度，的确如此，考虑一个全是1的数组，$target = 0$，任何时候$nums[mid] = nums[left]$，每次只会$left =left +1 $退化成线性复杂度。

我认为二分的边界转换就是不断的排除不可能的解，留下潜在的可行解。只要分析好在不同的情况，解空间会在什么范围内就一定不会把边界弄错。

C++ 代码

    bool search(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0) return false;
        int left = 0, right = n - 1;
        while(left <= right)
        {
            int mid = (left + right) / 2;
            if(nums[mid] == target) return true;
            else if(nums[mid] > nums[left])//左半区间非严格单调递增
            {
                //target是否在左半区间内
                if(target >= nums[left] && target < nums[mid]) right = mid - 1;
                else left = mid + 1;
            }else if(nums[mid] < nums[left])//右半区间严格单调递增
            {
                //target是否在右半区间内
                if(target > nums[mid] && target <= nums[right]) left = mid + 1;
                else right = mid - 1;
            }
            else//只能排除left不是一个可行解
                left++;
        }
        return false;
    }