#!/usr/bin/env python3

__author__ = 'Wei Mu'

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        if nums == []:
            return False
        
        if len(nums) == 1 and nums[0] == target:
            return True
        elif len(nums) == 1 and nums[0] != target:
            return False
        
        return self.helper_func(0, len(nums) - 1, target, nums)
    
    def helper_func(self, start, end, target, nums):
        if end - start == 1 and (nums[start] == target or nums[end] == target):
            return True
        elif end - start == 1 and (nums[start] != target or nums[end] != target):
            return False
        
        mid = (end + start) // 2
        
        if nums[start] == target or nums[mid] == target or nums[end] == target:
            return True
        
        if nums[start] == nums[mid] and nums[mid] == nums[end]:
            return (self.helper_func(start, mid, target, nums) or self.helper_func(mid, end, target, nums))
        
        if nums[start] > nums[mid]:
            if target > nums[start] or target < nums[mid]:
                end = mid
                return self.helper_func(start, end, target, nums)
            else:
                start = mid
                return self.helper_func(start, end, target, nums)
        
        elif nums[start] < nums[mid]:
            if target > nums[start] and target < nums[mid]:
                end = mid
                return self.helper_func(start, end, target, nums)
            else:
                start = mid
                return self.helper_func(start, end, target, nums)
        
        elif nums[start] == nums[mid] and target != nums[mid]:
            start = mid
            return self.helper_func(start, end, target, nums)
        elif nums[end] == nums[mid] and target != nums[mid]:
            end = mid
            return self.helper_func(start, end, target, nums)
