# https://leetcode.com/problems/search-in-rotated-sorted-array-ii/discuss/28195/Python-easy-to-understand-solution-(with-comments).
def search_rotated_array_2(nums, target):
    left, right = 0, len(nums)-1

    while left <= right:
        mid = (left+right//2)

        if nums[mid] == target:
            return True

        if left < mid and nums[left] == nums[mid]:
            left += 1
        
        if nums[left] <= nums[mid]:
            if nums[left] < target <= nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return False

if __name__ == "__main__":
    print(search_rotated_array_2([2,5,6,0,0,1,2], 0))