[Leetcode] 33. Search in Rotated Sorted Array

문제 바로가기

Binary Search (pivot + target)

Time Complexity: O(logn)
Space Complexity: O(1)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # find pivot with binary search
        n = len(nums)
        l, r = 0, n - 1
        while l < r:
            m = (l + r) // 2

            if nums[m] > nums[r]:
                l = m + 1
            else:
                r = m
            
        pivot = r
        
        # find target with binary search
        l, r = 0, n - 1
        while l <= r:
            m = (l + r) // 2
            rotatedM = (m + pivot) % n
            if nums[rotatedM] < target:
                l = m + 1
            elif nums[rotatedM] > target:
                r = m - 1
            else:
                return rotatedM
        
        return -1

Binary Search (target)

Time Complexity: O(logn)
Space Complexity: O(1)

그런데 사실 pivot을 찾지 않고도 한번의 binary search로 해결할 수도 있다.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        
        while l <= r:
            m = (l + r) // 2
            if target == nums[m]:
                return m
            
            # pivot이 mid보다 우측에 위치
            if nums[l] < nums[m]:
                if nums[l] <= target < nums[m]:
                    r = m -1
                else:
                    l = m + 1
            # pivot이 mid보다 좌측에 위치하거나 일치
            else:
                if nums[m] < target <= nums[r]:
                    l = m + 1
                else:
                    r = m - 1
                    
        return -1