34. Find First and Last Position of Element in Sorted Array (Array, Binary Search)

링크 - https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

우리는 Binary Search를 통해 문제를 풀 수 있다. 먼저, 우리는 mid의 값이 target과 같으면 expand하면서 답을 찾아 반환하면 된다. 그 뜻은 left와 right는 mid를 포함하지 않아도 된다는 것이다. 따라서 while문 조건은 left <= right가 되어야 하고, left = mid +1, right = mid - 1로 값을 업데이트 해야 한다.

Code

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

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

        return ans

Complexity

Time Complexity: O(logN) Binary Search로 하나의 원소를 찾는데 걸리는 시간이다.

Space Complexity: O(1)