81. Search in Rotated Sorted Arr

https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

对于一个有序数组，将其元素以某一个元素为轴进行旋转，比如[0,1,2,3,4,5,6,7]可能会变成[4,5,6,7,0,1,2,3]
求这个经过旋转的数组中是否存在有值等于target，如果有的话就返回其true，如果没有就返回false;数组中存在重复值

这里与search-in-rotated-sorted-array类似，也是先找到分界点，然后确定target在左边还是在右边；
注意点：

• 找最小值分界点时，由于存在重复值，需要在while循环加入 nums[lo]>=nums[hi] 判断，此时跳出循环后 hi 和 lo不一定相等
• 找到最小值分界点后，判断target在左边还是右边
• 去掉多余的重复值
• 再用一个二分查找去判断 target 是否存在

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size()-1;
        if(hi==-1)
            return false;
        while(lo < hi && nums[lo] >= nums[hi])
        {
            int mi = (lo + hi)>>1;
            if (nums[mi]<nums[hi])
                hi = mi;
            else if(nums[mi] > nums[hi])
                lo = mi + 1;
            else
                lo = lo + 1;
        }

        if(target <= nums[nums.size()-1])
        {
            lo = lo; hi = nums.size()-1;
        }
        else
        {
            hi = lo-1;
            lo = 0;
        }
        
        while(hi>=1 && nums[hi]==nums[hi-1])
            if(nums[hi]==target)
                return true;
            else
                hi-=2; //同时去掉两个相同的数值
        while(lo < hi)
        {
            int mi = (lo + hi)>>1;
            if (nums[mi] < target)
                lo = mi + 1;
            else
                hi = mi;
        }
        return nums[lo]==target;
    }
};

结果：

Runtime: 4 ms, faster than 98.90% of C++ online submissions for Search in Rotated Sorted Array II.
Memory Usage: 7.9 MB, less than 100.00% of C++ online submissions for Search in Rotated Sorted Array II.