회전된 정렬된 배열에서 검색 II

감소하지 않는 순서로 정렬된 정수 배열nums이 있습니다(반드시 고유 값이 있는 것은 아님).

함수에 전달되기 전에 nums는 알 수 없는 피벗 인덱스k(0 <= k < nums.length)에서 회전되어 결과 배열이 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](인덱스 0)가 됩니다. 예를 들어 [0,1,2,4,4,4,5,6,6,7]는 피벗 인덱스 5에서 회전하여 [4,5,6,6,7,0,1,2,4,4]가 될 수 있습니다.

회전 후 배열 nums과 정수 target가 주어지면 true가 target에 있으면 nums를 반환하고, false에 없으면 nums를 반환합니다.

전체 작업 단계를 최대한 줄여야 합니다.

예 1:

입력: 숫자 = [2,5,6,0,0,1,2], 대상 = 0
출력: 참

예 2:

입력: 숫자 = [2,5,6,0,0,1,2], 대상 = 3
출력: 거짓

제약:

1 <= nums.length <= 5000

-104 <= nums[i] <= 104

nums는 특정 피벗에서 회전하도록 보장됩니다.

-104 <= target <= 104

후속 조치: 이 문제는 와 유사하지만 nums에 중복이 포함될 수 있습니다. 이것이 런타임 복잡성에 영향을 줍니까? 어떻게 그리고 왜?

해결책:

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        # Initilize two pointers
        begin = 0
        end = len(nums) - 1 
        while begin <= end:
            mid = (begin + end)//2
            if nums[mid] == target:
                return True
            if nums[mid] == nums[end]: # Fail to estimate which side is sorted
                end -= 1  # In worst case: O(n)
            elif nums[mid] > nums[end]: # Left side of mid is sorted
                if  nums[begin] <= target and target < nums[mid]: # Target in the left side
                    end = mid - 1
                else: # in right side
                    begin = mid + 1
            else: # Right side is sorted
                if  nums[mid] < target and target <= nums[end]: # Target in the right side
                    begin = mid + 1
                else: # in left side
                    end = mid - 1
        return False