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

```//This question is the advanced version of question "Search in Rotated Sorted Array I"
//The key to solve it is to determine when to use linear search algorithm rather than an binary search one.
//When A[start] == A[end - 1], we have to search all the cases between [start, mid), and [mid, end)
//because we don't know where the pivot is. We can't shrink the search range unless A[mid] != A[start] and A[mid] != A[end - 1], which is a small possible incident.
class Solution {
public:
bool search(vector A,int target) {
int n = A.size();
if(n == 0){
return false;
}
return _search(A, 0, n, target);
}
bool _search(vector A, int start, int end, int target){
//base case
if(end - start == 1){
return A[start] == target;
}
int mid = (start + end) / 2;
if(A[start] == A[end - 1]){
//linear search
return _search(A, start, mid, target) || _search(A, mid, end, target);
}
else{
//binary search
if(A[start] < A[end - 1]){
if(target < A[mid]){                     return _search(A, start, mid, target);                 }                 else{                     return _search(A, mid, end, target);                 }             }             //pivot is between start and end - 1             else{                 if(A[mid] >= A[start]){
if(target >= A[mid]){
return _search(A, mid, end, target);
}
else{
if(target <= A[end - 1]){                             return _search(A, mid, end, target);                         }                         else{                             return _search(A, start, mid, target);                         }                     }                 }                 //mid is at the right of pivot                 else{                     if(target >= A[start]){
return _search(A, start, mid ,target);
}
else{
if(target < A[mid]){
return _search(A, start, mid, target);
}
else{
return _search(A, mid, end, target);
}
}
}
}
}
}
};``` This site uses Akismet to reduce spam. Learn how your comment data is processed.