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.

Solution:
Binary Search + find out the sorted half.
However, in the case of: 2,2,0,1,2, both half are not sorted, so we going to check both.

public class Solution {
    public Boolean search(int[] A, int target) {
        if(A.length == 0) return false;
        return binarySearch(A, target, 0, A.length-1);
    }
    public Boolean binarySearch(int[] A, int target, int first, int last){
        if(last < first) return false;
        int mid = (first + last) / 2;
        if(A[mid] == target) return true;
        // if left side is sorted
        if(A[first] < A[mid]){ 
            if(target >= A[first] && target <= A[mid-1]){
                return binarySearch(A, target, first, mid-1);
            }
            else return binarySearch(A, target, mid+1, last); 
        }
        // if right side is sorted
        else if(A[mid] < A[last]){ 
            if(target >= A[mid+1] && target <= A[last]){
                return binarySearch(A, target, mid+1, last);
            }
            else return binarySearch(A, target, first, mid-1);
        }
        // cannot make a decision
        else return (binarySearch(A, target, first, mid-1) || binarySearch(A, target, mid+1, last));  
    }
}