# Search in Rotated Sorted Array II

## Question

### Problem Statement

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.

## 题解

### C++

class Solution {
/**
* param A : an integer ratated sorted array and duplicates are allowed
* param target :  an integer to be search
* return : a boolean
*/
public:
bool search(vector<int> &A, int target) {
if (A.empty()) {
return false;
}

vector<int>::size_type start = 0;
vector<int>::size_type end = A.size() - 1;
vector<int>::size_type mid;

while (start + 1 < end) {
mid = start + (end - start) / 2;
if (target == A[mid]) {
return true;
}
if (A[start] < A[mid]) {
// situation 1, numbers between start and mid are sorted
if (A[start] <= target && target < A[mid]) {
end = mid;
} else {
start = mid;
}
} else if (A[start] > A[mid]) {
// situation 2, numbers between mid and end are sorted
if (A[mid] < target && target <= A[end]) {
start = mid;
} else {
end = mid;
}
} else  {
// increment start
++start;
}
}

if (A[start] == target || A[end] == target) {
return true;
}
return false;
}
};


### Java

public class Solution {
/**
* param A : an integer ratated sorted array and duplicates are allowed
* param target :  an integer to be search
* return : a boolean
*/
public boolean search(int[] A, int target) {
if (A == null || A.length == 0) return false;

int lb = 0, ub = A.length - 1;
while (lb + 1 < ub) {
int mid = lb + (ub - lb) / 2;
if (A[mid] == target) return true;

if (A[mid] > A[lb]) {
// case1: numbers between lb and mid are sorted
if (A[lb] <= target && target <= A[mid]) {
ub = mid;
} else {
lb = mid;
}
} else if (A[mid] < A[lb]) {
// case2: numbers between mid and ub are sorted
if (A[mid] <= target && target <= A[ub]) {
lb = mid;
} else {
ub = mid;
}
} else {
// case3: A[mid] == target
lb++;
}
}

if (target == A[lb] || target == A[ub]) {
return true;
}
return false;
}
}


### 源码分析

A[start] == A[mid]时递增start序号即可。