[LeetCode] 098: 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.

class Solution {
   
public:
	/**
	 * binary search
	 */
	int binarySearch(int A[], int left, int right, int target){
   
		int mid;
		while(left <= right){
   
			mid = left + (right-left)/2;
			if(target < A[mid]){
   
				right = mid - 1;
			}
			else if(target > A[mid]){
   
				left = mid + 1;
			}
			else{
   
				return mid;
			}
		}
		return -1;
	}
	/**
	 * search the bound of a rotated sorted array
	 */
	int binarySearchBound(int A[], int n, int left, int right){
   
		int mid;
		while(left <= right){
   
			mid = left + (right-left)/2;
			if(mid < n-1 && A[mid] > A[mid+1]){
   
				return mid;
			}
			else if(mid > 0 && A[mid] < A[mid-1]){
   
				return mid-1;
			}
			else if(A[mid] > A[left]){
   
				left = mid+1;
			}
			else if(A[mid] < A[right]){
   
				right = mid-1;
			}
			else if(A[mid] == A[left]){
   
				left++;
			}
			else if(A[mid] == A[right]){
   
				right--;
			}
		}
		return -1;
	}
	/**
	 * search in a rotated sorted array
	 */
	bool search(int A[], int n, int target) {
   
		// Note: The Solution object is instantiated only once and is reused by each test case.
		// invalid
		if(n <= 0)return -1;

		// binary search
		if(A[0] < A[n-1]){
   
			int res = binarySearch(A, 0, n-1, target);
			if(res != -1)return true;
		}

		// search the bound
		int bound = binarySearchBound(A, n, 0, n-1);

		// binary search the left part
		int left = binarySearch(A, 0, bound, target);
		if(left != -1)return true;

		// binary search the right part
		int right = binarySearch(A, bound+1, n-1, target);
		return right == -1 ? false : true;
	}
};