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.

---

There are several special cases to consider for this problem. By binary search, what if the start element is equal to the mid element? There are two possibilities: one is all elements from start to mid are equal to each other. The other one is may be some of the elements from start to mid are equal to each other. For the latter case, we can only shrink the search range by one element.

C++ Code:

/*
 * func: search_rotated_array_helper
 * goal: helper function for search_rotated_array
 * @param A: input array A
 * @param start: start index
 * @param end: end index
 * @param target: target value
 * return: True or False
 */
bool search_rotated_array_helper(int A[], int start, int end, int target){
    if(start >= end){
        return A[start] == target;
    }
    
    int mid = start + (end-start)/2;
    
    if(A[mid] == target){
        return true;
    }else if(A[start] < A[mid]){
        if(A[start] <= target && target < A[mid])
            return search_rotated_array_helper(A, start, mid-1, target);
        else
            return search_rotated_array_helper(A, mid+1, end, target);
    }else if(A[start] == A[mid]){
        return search_rotated_array_helper(A, mid+1, end, target);
    }else{
        if(A[mid] < target && target <= A[end])
            return search_rotated_array_helper(A, mid+1, end, target);
        else
            return search_rotated_array_helper(A, start, mid-1, target);
    }
}

/*
 * func: search_rotated_array
 * goal: search the target in a rotated sorted array where duplicates exist
 * @param A: input array
 * @param n: size of the array
 * @param target: target
 * return: true or false
 */
bool search_rotated_array(int A[], int n, int target){
    return search_rotated_array_helper(A, 0, n-1, target);
}

Python Code:

# func: search target in rotated sorted array
# @param A: input array
# @param target: target
# @return: True or False
def search_rotated_array(A, target):
    start = 0
    end = len(A)-1
    while start < end:
        mid = start + (end-start)/2
        if A[mid] == target:
            return True
        elif A[start] < A[mid]:
            if A[start] <= target < A[mid]:
                end = mid - 1
            else:
                start = mid + 1
        elif A[start] == A[mid]:
            start += 1
        else:
            if A[mid] < target <= A[end]:
                start = mid + 1
            else:
                end = mid - 1
    return A[start] == target