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

Algorithm:

The difference here is that how to handle when A[mid] == A[right]!

then we can not decide the pivot location when A[mid] == A[right]. My solution is that when this happens, just move right to left until A[mid] != A[right].

There may be better solutions, can update later.

My Code:

bool RS(int A[], int left, int right, int target){
        if(right < left) return false;
        if(left == right) {
            if(A[left] == target) return true;
            else return false;
        }
        int mid = (left+right)/2;
        if(A[mid] == target) return true;
        if(A[mid] == A[right]){
            while(A[mid] == A[right] && right >= 0){
                right--;
            }
            return RS(A, left, right, target);
        }
        else if(A[mid] < A[right]){
            // rotated pivot on the left
            if(target < A[mid]) return RS(A, left, mid-1, target);
            else{
              if(target > A[right]) return RS(A, left, mid-1, target);
              else return RS(A, mid+1, right, target);
            }
        } else {
            //rotated pivot on the right
            if(target > A[mid]) return RS(A, mid+1, right, target);
            else{
              if(target > A[right]) return RS(A, left, mid-1, target);
              else return RS(A, mid+1, right, target);
            }
        }
    }
bool search(int A[], int n, int target) {
        if(n <= 0) return false;
        return RS(A, 0, n-1, target);
}