Note: This article is available in Chinese only. 本文暂无英文版本。
View original
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的时候。。。缩小范围。。。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年04月05日 星期三 20时26分25秒
4File Name :81.cpp
5************************************************ */
6
7
8
9class Solution {
10
11public:
12
13 bool search(vector<int>& nums, int target) {
14 int siz = nums.size();
15 if (siz==0) return false;
16 int l = 0 ;
17 int r = siz-1;
18 while (l<=r)
19 {
20 int mid = (l+r)>>1;
21 if (nums[mid]==target) return true;
22 if (nums[l]<nums[mid])
23 {
24 if (nums[l]<=target&&target<nums[mid])
25 r = mid - 1;
26 else
27 l = mid + 1;
28 }
29 else if (nums[mid]<nums[r])
30 {
31 if (nums[mid]<target&&target<=nums[r]) l = mid + 1;
32 else r = mid -1;
33 }
34 else if (nums[l]==nums[mid]) l++;
35 else if (nums[mid]==nums[r]) r--; //nums[l]或nunms[r] is not the target,so remove it..重复元素最烦人了。。。
36 }
37
38 return false;
39
40 }
41
42};