class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        
        left, right = 0, len(nums)-1
        
        while left<=right:
            mid = left+(right-left)//2
            
            if nums[mid]==target:
                return True
            
            while left < mid and nums[left] == nums[mid]: # tricky part
                left += 1
            
            if nums[mid]>=nums[left]:
                if target>=nums[left] and target<nums[mid]:
                    right = mid-1
                else:
                    left = mid+1
            else:
                if target>nums[mid] and target<=nums[right]:
                    left = mid+1
                else:
                    right = mid-1
        
        return False