[LeetCode] Search in Rotated Sorted Array II

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.

分析
如果允许重复元素，则Search in Rotated Sorted Array题中如果 A[m]>=A[l], 那么 [l,m] 为递增序列的假设就不能成立了，比
如 [1,2，3,1,1,1]。
如果 A[m]>=A[l] 不能确定递增，那就把它拆分成两个条件：
• 若 A[m]>A[l]，则区间 [l,m] 一定递增
• 若 A[m]==A[l] 确定不了，那就 l++，往下看一步即可。

Search in Rotated Sorted Array 的code：

 1 class Solution {
 2 public:
 3     bool search(int A[], int n, int target) {
 4         int low = 0;
 5         int high = n-1;
 6         int mid ;
 7 
 8         
 9         while(low<=high)
10         {
11             mid= (low + high)/2;
12             
13             if(A[mid]==target)
14             {
15                 return true;
16             }
17                     
18             if(A[low]<=A[mid]) // the pivot is in the bottom half
19             {
20                 if(A[low]<=target && target < A[mid]) //target in the first half
21                     high = mid-1;
22                 else
23                     low = mid+1;//target in the bottom half
24             }
25             else // the pivot is in the first half
26             {
27                 if(A[mid] < target && target <= A[high])// the pivot is in the first half
28                     low = mid+1;
29                 else //target in the first half
30                     high = mid-1;
31             }
32             
33         }
34         return false;
35         
36     }
37 };

将if (A[low] <= A[mid]) 拆成if (A[low] < A[mid]) 和 if (A[low] == A[mid]) 两个分支，code如下：

 1 class Solution {
 2 public:
 3     bool search(int A[], int n, int target) {
 4         int low = 0;
 5         int high = n-1;
 6         int mid ;
 7 
 8         
 9         while(low<=high)
10         {
11             mid= (low + high)/2;
12             
13             if(A[mid]==target)
14             {
15                 return true;
16             }
17                     
18             if(A[low]<A[mid])
19             {
20                 if(A[low]<=target && target < A[mid])
21                     high = mid-1;
22                 else
23                     low = mid+1;
24             }
25             else if(A[low] > A[mid])
26             {
27                 if(A[mid] < target && target <= A[high])
28                     low = mid+1;
29                 else 
30                     high = mid-1;
31             }
32             else 
33                 low++;
34             
35         }
36         return false;
37         
38     }
39 };