当没有重复元素时, A[left] <= A[mid]表示右边部分是rotated的。当有重复的元素时, A[left] <= A[mid]要分开讨论了, 比如A=[1,3,1,1,1], left = 0, right = 4, mid = 2, 虽然A[left] <= A[mid], 但是rotated的部分在左边。此时A[left] < A[mid]才表示右边部分是rotated,  A[left] == A[mid]时left++即可。

When there's no duplicate, A[left] <= A[mid] means the right part is rotated. When there are duplicates, A[left] <= A[mid] is not certain. E.g. A=[1,3,1,1,1], left = 0, right = 4, mid = 2, although A[left] <= A[mid], the left part is rotated. Here A[left] < A[mid] means the right part is rotated, when A[left] == A[mid] just left ++.

class Solution:
    # @param A a list of integers
    # @param target an integer
    # @return a boolean
    def search(self, A, target):
        left, right = 0, len(A) - 1
        while left <= right:
            mid = (left + right) / 2
            if A[mid] == target: return True
            if A[left] < A[mid]: # the right part is rotated
                if A[left] <= target < A[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            elif A[left] > A[mid]: # the left part is rotated
                if A[mid] < target <= A[right]:
                    left = mid + 1
                else:
                    right = mid - 1
            else: # A[left] == A[mid]
                left += 1
        return False