# https://oj.leetcode.com/problems/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.


# This follows the solution in http://blog.csdn.net/linhuanmars/article/details/20588511
# The idea is to single out the case where the middle element equals boundary element.
class Solution:
    # @param A a list of integers
    # @param target an integer
    # @return a boolean
    def search(self, A, target):
        if len(A) == 0:
            return False

        L = 0
        R = len(A) -1
        while L<=R:
            M = (L+R)/2
            if A[M] == target:
                return True

            # The idea is to operate on the subarray that is not rotated
            if A[M] < A[R]:    # right-side subarray is not rotated
                #print 'Case 1'
                if A[M]<target and A[R]>=target:
                    L = M+1
                else:
                    R = M-1
            elif A[M] > A[R]:  # right-side subarray is rotated, meaning the left-side
                               # subarray may be non-rotated
                #print 'Case 2'
                if A[M]>target and A[L]<=target:
                    R = M-1
                else:
                    L = M+1
            else:  # if A[M]==A[R], pull back the right boundary until A[M]!=A[R]
                #print 'Case 3'
                R -= 1
        return False

# s = Solution()
# print s.search([1,2,3,4,5,5,5,5,5,], 3)
