題目：
假設按照升序排序的數(shù)組在預先未知的某個點上進行了旋轉灰羽。

( 例如蜓肆，數(shù)組 [0,0,1,2,2,5,6] 可能變?yōu)?[2,5,6,0,0,1,2] )元媚。

編寫一個函數(shù)來判斷給定的目標值是否存在于數(shù)組中。若存在返回 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

鏈接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii

思路：
1、這道題是二分查找法的變種蒙畴。首先定義左右指針贰镣，中間指針呜象。
2、需要遍歷去掉左右節(jié)點的重復數(shù)據(jù)
3碑隆、數(shù)據(jù)有五種情況：
a）mid位置的值和target一樣恭陡，完美，返回true
b）mid位置的值大于等于left位置的值上煤，說明從left到mid部分的順序是遞增的
i）如果target在left到mid之間休玩，說明mid太大了，需要right左移
ii）否則劫狠，left左移
c）mid位置的值比left位置的值小拴疤，說明mid到right部分的順序是遞增的
i）如果target在mid到right之間，說明mid偏小了独泞，需要將left右移
ii）否則right左移

Python代碼：

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        left = 0
        right = len(nums)-1

        while left<=right:
            # 去掉左右的重復數(shù)據(jù)
            while (left<right and nums[left]==nums[left+1]):
                left += 1
            while (left<right and nums[right]==nums[right-1]):
                right -= 1
            mid = (left+right)/2
            if nums[mid]==target:
                return True
            if nums[mid]>=nums[left]:  # 從left位置到mid是有序的
                # 如果target在left到mid之間遥赚，說明mid大了，需要right左移
                if(target>=nums[left] and target<nums[mid]):
                    right = mid-1
                else:
                    left =mid+1
            else: # 從mid位置到right位置是有序的
                # 如果target在mid到right之間阐肤，說明mid小了，需要left右移
                if (target>nums[mid] and target<=nums[right]):
                    left = mid+1
                else:
                    right = mid-1
        return False

C++代碼：

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size()-1;

        while(left<=right){
            while(left<right && nums[left]==nums[left+1]){
                left += 1;
            }
            while(left<right && nums[right]==nums[right-1]){
                right -= 1;
            }
            int mid = (left+right)/2;
            if(nums[mid]==target) return true;
            if(nums[mid]>=nums[left]){ // 從left到mid是有序的
                if(target>=nums[left] && target<nums[mid]){  // left target mid right
                    right = mid-1;
                }else{
                    left = mid+1;
                }
            }else{ // 從mid到right是有序的
                if(target>nums[mid] && target<=nums[right]){ // left mid target right
                    left = mid+1;
                }else{
                    right = mid-1;
                }
            }
        }
        return false;
    }
};