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/editorial/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

이 문제는 Binary Search알고리즘으로 풀 수 있다. 

1. left와 right를 0, len(nums) - 1로 초기화 한다.

2. while문에서 left<=right인 조건을 주고 돌린다.

3. mid = left + (right-left)//2 로 구한다. 만약 nums[mid]가 target에 맞으면, 우리는 거기서 linear하게 left와 right를 찾은뒤, 답을 반환한다.

4. nums[mid]가 target보다 작으면, 우리는 오른쪽 구역에서 답을 찾아야 한다. 따라서 left = mid+1로 설정한다.

5. nums[mid]가 target보다 크면, 우리는 왼쪽 구역에서 답을 찾아야 한다. 따라서 right = mid-1로 설정한다.

Code

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left, right = 0, len(nums) - 1
        ans = [-1, -1]

        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                mid_left, mid_right = mid, mid
                while mid_left >= 0 and nums[mid_left] == target:
                    ans[0] = mid_left
                    mid_left -= 1
                while mid_right < len(nums) and nums[mid_right] == target:
                    ans[1] = mid_right
                    mid_right += 1
                return ans
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return ans

Complexity

Time Complexity: O(logn) binary search로 n개의 원소들중에서 답을 찾으므로 O(logn)이 된다.

Space Complexity: O(1) 상수 변수만을 사용하기 때문에 O(1)이다.