## Thursday, January 3, 2013

### [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.
» Solve this problem

[解题思路]

[1,3,1,1,1]

1. 对于每一个递增序列，遍历之，确认。
2. 找到pivot点，然后确定对应序列搜索。

1. A[m]>A[l]  递增
2. A[m] ==A[l] 确定不了，那就l++，往下看一步即可。

``````1:       bool search(int A[], int n, int target) {
2:            int start = 0;
3:            int end = n-1;
4:            while(start <= end)
5:            {
6:                 int mid = (start+end)/2;
7:                 if(A[mid] == target) return true;
8:                 if(A[start] < A[mid])
9:                 {
10:                      if(target>=A[start] && target<A[mid])
11:                           end = mid-1;
12:                      else
13:                           start = mid+1;
14:                 }
15:                 else if(A[start] > A[mid])
16:                 {
17:                      if(target>A[mid] && target<=A[end])
18:                           start = mid+1;
19:                      else
20:                           end = mid-1;
21:                 }
22:                 ``````else //skip duplicate one, A[start] == A[mid]
23:                      start++; ``````
24:            }
25:            return false;
26:       }
``````