[Leetcode] 34. Find First and Last Position of Element in Sorted Array

문제 바로가기

처음 풀이

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

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        found = False
        l, r, = 0, n - 1
        foundPos = None

        # find target
        while l <= r:
            m = (l + r) // 2
            if nums[m] < target:
                l = m + 1
            elif nums[m] > target:
                r = m - 1
            else:
                found = True
                foundPos = m
                break
                
        if not found:
            return [-1, -1]
        
        # find first position in a partial list nums[0:m]
        r1 = foundPos - 1  # temp right pointer
        while l <= r1:
            m = (l + r1) // 2
            if nums[m] < target:
                l = m + 1
            else:
                r1 = m - 1
        # target doesn't exist in the partial list
        if nums[l] < target:
            l += 1
        
        # find last position in a partial list nums[m+1:]
        l1 = foundPos + 1  # temp left pointer
        while l1 <= r:
            m = (l1 + r) // 2
            if nums[m] > target:
                r = m - 1
            else:
                l1 = m + 1
        # target doesn't exist in the partial list
        if nums[r] > target:
            r -= 1
        
        return [l, r]

함수 작성 및 recursion

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

처음에 target이 있는지 찾을 필요도 없이 바로 처음 마지막 위치를 binary search로 찾는다.
빈 list의 경우 길이가 0인데 탐색 시작위치 l에 0이 들어간다. 따라서 편의를 위해 r에 n-1이 아닌 n을 넣어 l이 n에 도달하면 [-1,-1]을 반환하도록 한다. (n: 리스트의 길이)
이는 이진 탐색의 중간값이 최대 r-1까지 가능하기 때문에 가능하다.

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def bSearch(l: int, r: int, startSearch: bool) -> int:
            if l < r:
                m = (l + r) // 2
                if nums[m] > target or (startSearch and nums[m] == target):
                    return bSearch(l, m, startSearch)
                else:
                    return bSearch(m + 1, r, startSearch)
            else:
                return l

        n = len(nums)
        start = bSearch(0, n, True)
        if start == n or nums[start] != target:
            return [-1, -1]
        end = bSearch(0, n, False) - 1
        return [start, end]