LeetCode: 81. Search in Rotated Sorted Array II

이 문제는 아래 문제와 상당히 유사하다.

33. Search in Rotated Sorted Array (https://leetcode.com/problems/search-in-rotated-sorted-array/description/)

실제 구현도 유사하지만, Time Complexity는 다른데 그 이유를 생각해보면 흥미롭다.

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