LeetCode 풀기 - 34. Find First and Last Position of Element in Sorted Array

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

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

문제)

솔루션1) binary search

풀이 순서:

1) 바이너리 서치로 target을 탐색

2) 찾은 target에서 왼쪽으로 인덱스를 이동하면서 동일한 target 값이 나올 때 까지 이동 (left idx)

3) 찾은 target에서 오른쪽 인덱스를 이동하면서 동일한 target 값이 나올 때 까지 이동 (right idx)

위 풀이는 결국 시간 복잡도 O(n)을 갖기 때문에 O(logn)을 만족하지 못 합니다.

 

 

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:        
        def search():
            left = 0
            right = len(nums)
            while left < right:
                mid = (left+right)//2
                if nums[mid] == target:
                    return mid
                elif nums[mid] < target:
                    left = mid+1
                else:
                    right = mid
            return -1
        
        target_idx = search()        
        if target_idx == -1:
            return [-1, -1]
        
        # left idx
        left_idx = target_idx
        while left_idx > 0 and nums[left_idx-1] == target:
            left_idx -= 1

        # right idx
        right_idx = target_idx
        while right_idx < (len(nums)-1) and nums[right_idx+1] == target:
            right_idx += 1
        return [left_idx, right_idx]

솔루션2) binary search

discuss에 아주 멋진 솔루션이 있네요.

binary search를 조금 변형해서 원하는 target의 가장 왼쪽 idx를 찾도록 조금 변경된 코드입니다.

이것을 이용하면 target의 가장 오른쪽 idx도 동일하게 찾을 수 있습니다.

바이너리 서치를 두 번 호출하지만 시간 복잡도는 O(logn)을 만족합니다.

 

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

함께 보면 좋은 글:

2021.11.10 - [알고리즘/알고리즘 Basic] - [파이썬] 바이너리 서치 (이진 탐색)

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/discuss/1054742/Python-O(logn)