【Search in Rotated Sorted Array II 】cpp

题目：

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

代码：

class Solution {
public:
    bool search(vector<int>& nums, int target) {
            nums.erase(std::unique(nums.begin(), nums.end()),nums.end());
            int begin=0, end=nums.size()-1;
            while ( begin<=end )
            {
                int mid = (begin+end)/2;
                if ( nums[mid]==target ) return true;
                // first half sorted
                if ( nums[begin]<=nums[mid] )
                {
                    if ( target>nums[mid] )
                    {
                        begin = mid+1;
                    }
                    else
                    {
                        if ( target>=nums[begin] )
                        {
                            end = mid-1;
                        }
                        else
                        {
                            begin = mid+1;
                        }
                    }
                    continue;
                }
                // second half sorted
                if ( nums[mid]<nums[end] )
                {
                    if ( target<nums[mid])
                    {
                        end = mid-1;
                    }
                    else
                    {
                        if ( target<=nums[end])
                        {
                            begin = mid+1;
                        }
                        else
                        {
                            end = mid-1;
                        }
                    }
                }

            }
            return false;
    }
};

tips：

通过这题熟悉了stl将vector去重的方法。

采用了偷懒的做法：

1. 先利用stl的unqiue把数组去重

2. 再按照Search in Rotated Sorted Array这题的方法进行二分查找。