# leetcode 81. Search in Rotated Sorted Array II (有重复元素的旋转数组找给定值)

Posted by 111qqz on Wednesday, April 5, 2017

## TOC

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

(i.e., `0 1 2 4 5 6 7` might become `4 5 6 7 0 1 2`).

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

The array may contain duplicates.

``````/* ***********************************************
Author :111qqz
Created Time :2017年04月05日 星期三 20时26分25秒
File Name :81.cpp
************************************************ */

class Solution {

public:

bool search(vector<int>& nums, int target) {
int siz = nums.size();
if (siz==0) return false;
int l = 0 ;
int r = siz-1;
while (l<=r)
{
int mid = (l+r)>>1;
if (nums[mid]==target)  return true;
if (nums[l]<nums[mid])
{
if (nums[l]<=target&&target<nums[mid])
r = mid - 1;
else
l = mid + 1;
}
else if (nums[mid]<nums[r])
{
if (nums[mid]<target&&target<=nums[r]) l = mid + 1;
else r = mid -1;
}
else if (nums[l]==nums[mid]) l++;
else if (nums[mid]==nums[r]) r--;   //nums[l]或nunms[r] is not the target,so remove it..重复元素最烦人了。。。
}

return false;

}

};
``````