[LEETCODE] 34: Find First and Last Position of Element in Sorted Array(Python)

Find First and Last Position of Element in Sorted Array - LeetCode

문제 설명

오름차순 정렬된 배열에서 타겟이 등장한 처음 인덱스와 끝 인덱스를 찾아보자. 만약 타겟이 존재하지 않는다면 [-1, -1]을 출력한다.

나의 풀이

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        n=len(nums)
        answer=[n,-1]
        s=0
        e=n-1
        while s<=e:
            m=(s+e)//2
            if nums[m]>=target:
                e=m-1
                if nums[m]==target:
                    answer[0]=m
            else: # nums[m]<target:
                s=m+1
        
        s=0
        e=n-1
        while s<=e:
            m=(s+e)//2
            if nums[m]<=target:
                s=m+1
                if nums[m]==target:
                    answer[1]=m
            else: # nums[m]>target:
                e=m-1
                
        if answer==[n,-1]:
            answer=[-1,-1]
            
        return answer

단순히 순회를 해도 되지만 문제 조건에서 logN 복잡도로 풀라고 되어 있기 때문에 이분 탐색을 사용했다. 처음에는 answer를 탐색이 전부 끝난 뒤에 업데이트하려고 했는데, 그것보다는 타겟을 발견했을 때마다 업데이트했다.

시간복잡도

이분탐색을 두 번 사용해므로 O(2*logn)이다.