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

Leetcode #34 - Find First and Last Position of Element in Sorted Array

이번에는 특정 챕터별로 문제들을 풀어보겠습니다. string을 집중적으로 풀어보겠습니다.

리트코드의 문제 34 ‘Find First and Last Position of Element in Sorted Array’을 파이썬으로 풀어 보도록 하겠습니다.

포인트는 이진탐색으로 구현하면서 시작점과 끝점을 따로 구해주는 것입니다.

전체 코드는 아래와 같습니다.

class Solution:
    def searchRange(self, nums, target):
        if not nums:
            return [-1, -1]
        
        if target < nums[0] or nums[-1] < target:
            return [-1, -1]
        
        low, high = 0, len(nums)-1
        
        start, end = -1,-1
        while low <= high:
            mid = (low + high)//2

            if target < nums[mid]:
                high = mid - 1
            elif nums[mid] < target:
                low = mid + 1
            else:
                # original binary tree
                # for start
                for i in range(low, mid+1):
                    if nums[i] == target:
                        start = i
                        break
                # for end
                for i in range(high, mid-1, -1):
                    if nums[i] == target:
                        end = i
                        break
                return [start, end]
            
        return [start, end]

시간복잡도는 O(logn) : 이진탐색 구현(logn)

• 최악의 경우에는 for loop로 (n/2) low가 0이고 high가 len(n)에 중간 값만(mid) target과 일치할 경우

공간복잡도는 O(1) : 상수 low,high,mid 구현