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);
                        }
                    }
                }
            }
        }
    }
};