Leetcode 34. Find First and Last Position of Element in Sorted Array with Python - 리뷰 O

문제

Given an array of integers nums sorted in non-decreasing order, 
find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

오름차순으로 정렬된 배열 nums에 대해 특정 target 숫자의 범위를 리스트로 리턴하시오.
숫자가 없을시 [-1, -1] 을 리턴하면 됩니다.

예시

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

제한

• 0 <= nums.length <= 105
• 10^9 <= nums[i] <= 10^9
• nums is a non-decreasing array.
• 10^9 <= target <= 10^9

풀이

특정 값의 왼쪽 끝을 찾는 binary search와 오른쪽 끝을 찾는 binary search를 두번 사용해 풀었다.

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # 찾지 못하면 [-1, -1] 리턴됨.
        left = right = -1
        start = 0
        end = len(nums)-1
        # 값의 왼쪽 끝 위치를 찾기 위한 Binary search
        while start <= end:
            mid = (start + end) // 2
            if (nums[mid] == target) and ((mid > 0 and nums[mid-1] != target) or (mid == 0)):
                left = mid
                break
            elif nums[mid] >= target:
                end = mid - 1
            else:
                start = mid + 1
        start = 0
        end = len(nums)-1
        # 값의 오른쪽 끝을 찾기 위한 Binary search
        while start <= end:
            mid = (start + end) // 2
            if (nums[mid] == target) and ((mid < len(nums)-1 and nums[mid+1] != target) or (mid == len(nums)-1)):
                right = mid
                break
            elif nums[mid] <= target:
                start = mid + 1
            else:
                end = mid - 1
        return [left, right]
        

O(logN) 의 시간복잡도를 가지는 binary search가 두번 사용되어 시간복잡도는 O(logN) 이다.

(2024 / 12 / 02)

복기

• bisect 함수를 사용한다.

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left = bisect_left(nums, target)
        right = bisect_right(nums, target)

        if left >= len(nums) or nums[left] != target:
            return [-1, -1]
        else:
            return [left, right - 1]

• 직접 bisect를 최대한 적절하게 구현도 해보았다.

def left(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1

    ans = -1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        else:
            ans = mid
            right = mid - 1

    return ans

def right(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1

    ans = -1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        else:
            ans = mid
            left = mid + 1

    return ans


class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        l = left(nums, target)
        r = right(nums, target)

        if left == -1:
            return [-1, -1]
        else:
            return [l, r]