# [LeetCode 81] Search in Rotated Sorted Array II

### Question

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.

### Stats

 Frequency 3 Difficulty 5 Adjusted Difficulty 4 Time to use --------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

### Analysis

This one is based on the solution of previous question.

The previous question is already very difficult, both the logic and coding part. However, if you solve previous question by yourself, you will do this one easily.

I will pick the 2nd piece of code in previous question, and modify it to solve this problem.

Solution for previous question:

``````public int search(int[] A, int target) {
int left = 0;
int right = A.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (target == A[mid]) return mid;
if (A[left] <= A[mid]) {
if (A[left] <= target && target <= A[mid]) right = mid;
else left = mid + 1;
} else {
if (A[mid] <= target && target <= A[right]) left = mid;
else right = mid - 1;
}
}
return -1;
}
``````

### Solution

My solution is to skip all duplicated numbers before the while-loop.

The most standard solution is left-pointer incremental. A good code is written from this blog.

### Code

First, my solution

``````public boolean search(int[] A, int target) {
int len = A.length, L = 0, R = len - 1;
if (A[L] == A[R]) {
int duplicate = A[R];
if (duplicate == target) return true;
while (L < len && A[L] == duplicate) L ++;
while (R >= 0 && A[R] == duplicate) R --;
}
while (L <= R) {
// Avoid overflow, same as M=(L+R)/2
int M = L + ((R - L) / 2);
if (A[M] == target) return true;
// the bottom half is sorted
if (A[L] <= A[M])
if (A[L] <= target && target < A[M]) R = M - 1;
else L = M + 1;
// the upper half is sorted
else
if (A[M] < target && target <= A[R]) L = M + 1;
else R = M - 1;
}
return false;
}
``````

Second, standard solution

``````public boolean search(int[] A, int target) {
int len = A.length, L = 0, R = len - 1;
while (L <= R) {
int M = L + ((R - L) / 2);
if (A[M] == target) return true;
if (A[L] < A[M])
if (A[L] <= target && target < A[M]) R = M - 1;
else L = M + 1;
else if (A[L] > A[M])
if (A[M] < target && target <= A[R]) L = M + 1;
else R = M - 1;
else L ++;
}
return false;
}
``````