leetcode 81. Search in Rotated Sorted Array II (有重复元素的旋转数组找给定值)
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.
好像阿里一面的时候问过。。。
思路：肯定是二分。。。不过由于有重复元素。。。所以很恶心。。。
总的思路是。。。当发现重复元素。。并且该重复元素不是target的时候。。。缩小范围。。。
/* ***********************************************
Author :111qqz
Created Time :2017年04月05日 星期三 20时26分25秒
File Name :81.cpp
************************************************ */
class Solution {
public:
1 bool search(vector<int>& nums, int target) {
2 int siz = nums.size();
3 if (siz==0) return false;
4 int l = 0 ;
5 int r = siz-1;
6 while (l<=r)
7 {
8 int mid = (l+r)>>1;
9 if (nums[mid]==target) return true;
10 if (nums[l]<nums[mid])
11 {
12 if (nums[l]<=target&&target<nums[mid])
13 r = mid - 1;
14 else
15 l = mid + 1;
16 }
17 else if (nums[mid]<nums[r])
18 {
19 if (nums[mid]<target&&target<=nums[r]) l = mid + 1;
20 else r = mid -1;
21 }
22 else if (nums[l]==nums[mid]) l++;
23 else if (nums[mid]==nums[r]) r--; //nums[l]或nunms[r] is not the target,so remove it..重复元素最烦人了。。。
24 }
return false;
}
};