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.

思路：跟【Leetcode】Search in Rotated Sorted Array类似，但是需要做些许改动，因为对于递增序列的判断需要增加一些条件。当然，此题的解答也能解决上一题的问题。

代码一：

class Solution {
public:
    bool search(int A[], int n, int target) {
        if(n <= 0)  return false;
        
        int left = 0;
        int right = n - 1;
        int middle = 0;
        
        while(left <= right)
        {
            middle = (left + right) / 2;
            
            if(A[middle] == target)
                return true;
            else if(A[middle] < target)
            {
                if(A[left] == A[middle])    
                    left++;
                else if(A[left] > A[middle] && A[right] < target)
                    right = middle - 1;
                else
                    left = middle + 1;
            }
            else
            {
                if(A[right] == A[middle])   
                    right--;
                else if(A[right] < A[middle] && A[left] > target)
                    left = middle + 1;
                else
                    right = middle - 1;
            }
        }
        
        return false;
    }
};

class Solution {
public:
    bool search(int A[], int n, int target) {
        if(n <= 0)  return false;
        
        int left = 0;
        int right = n - 1;
        int middle = 0;
        
        while(left <= right)
        {
            middle = (left + right) / 2;
            
            if(A[middle] == target)
                return true;
            
            if(A[left] < A[middle])
            {
                if(A[left] <= target && target < A[middle])
                    right = middle - 1;
                else
                    left = middle + 1;
            }
            else if(A[left] > A[middle])
            {
                if(A[middle] < target && target <= A[right])
                    left = middle + 1;
                else
                    right = middle - 1;
            }
            else
                left++;
        }
        
        return false;
    }
};