2014
11-18

# LeetCode-Search in Rotated Sorted Array II[数组]

### 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.

\item 若{A[m]>A[l]}，则区间{[l,m]}一定递增
\item 若{A[m]==A[l]} 确定不了，那就{l++}，往下看一步即可。

// LeetCode, Search in Rotated Sorted Array II
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
bool search(int A[], int n, int target) {
int first = 0, last = n;
while (first != last) {
const int mid = (first + last) / 2;
if (A[mid] == target)
return true;
if (A[first] < A[mid]) {
if (A[first] <= target && target < A[mid])
last = mid;
else
first = mid + 1;
} else if (A[first] > A[mid]) {
if (A[mid] < target && target <= A[last-1])
first = mid + 1;
else
last = mid;
} else
//skip duplicate one
first++;
}
return false;
}
};


Java代码:

public class Solution {
public static boolean search(int[] A, int target) {
return searchBinary(A, 0, A.length-1 , target);
}

public static boolean searchBinary(int A[],int s,int e,int target){
int mid = (s+e)/2;

if(A[mid] == target)
return true;
if(s >= e) return false;
if( A[mid] < A[e] ){ //后半部分是顺序的
if(target > A[mid] && target <= A[e]){
return searchBinary(A, mid+1, e, target);
}else
return searchBinary(A, s, mid-1, target);
}else if(A[mid] > A[e]){ //前半部分顺序的
if(target >= A[s] && target < A[mid])
return searchBinary(A, s, mid-1, target);
else
return searchBinary(A, mid+1, e, target);
}else{ //相等时，无法判断
for(int i=s; i<=e; i++)
if(A[i] == target) return true;
return false;
}

}
}

1. 第二种想法，我想来好久，为啥需要一个newhead，发现是把最后一个节点一直返回到嘴上面这层函数。厉害，这道题之前没样子想过。

2. 是穷举，但是代码有优化（v数组），并不是2^n。测试数据应该没问题，之前有超时的代码。

3. a是根先忽略掉，递归子树。剩下前缀bejkcfghid和后缀jkebfghicd，分拆的原则的是每个子树前缀和后缀的节点个数是一样的，根节点出现在前缀的第一个，后缀的最后一个。根节点b出现后缀的第四个位置，则第一部分为四个节点，前缀bejk，后缀jkeb，剩下的c出现在后缀的倒数第2个，就划分为cfghi和 fghic，第3部分就为c、c

4. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.