leetcode--81--搜索旋转排序数组 II

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

( 例如，数组 [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

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

思路：
1、这道题是二分查找法的变种。首先定义左右指针，中间指针。
2、需要遍历去掉左右节点的重复数据
3、数据有五种情况：
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:
            # 去掉左右的重复数据
            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;
    }
};