[파이썬] LeetCode 34. Find First and Last Position of Element in Sorted Array 👉🏻 이분 탐색

🔗 문제

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

👀 이분탐색

이분탐색과 관련하여 자세한 내용은 아래 포스팅에 정리되어 있다.

👉🏻 이분탐색 더 알아보기

👩🏻‍💻 답안

🚨 이분탐색 문제에서 주의할 점

• while left + 1 < right를 사용하면 mid + 1 / mid - 1 이런 식으로 할 필요가 없다.
• left, right의 초기값을 답이 될 수 있는 값으로 설정하지 말 것 (그보다 하나 적고, 하나 큰 값으로 설정할 것)

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums or target not in nums:
            return [-1, -1]

        # 가장 첫 번째로 target이 되는 인덱스 찾기
        def find_first_occurrence(nums, target):
            left, right = -1, len(nums)
            while left + 1 < right:
                mid = (left + right) // 2
                if nums[mid] < target:
                    left = mid
                else:
                    right = mid

            return right

        # 가장 마지막으로 target이 되는 인덱스 찾기
        def find_last_occurrence(nums, target):
            left, right = -1, len(nums)
            while left + 1 < right:
                mid = (left + right) // 2
                if nums[mid] <= target:
                    left = mid
                else:
                    right = mid

            return left

        first_occurrence = find_first_occurrence(nums, target)
        last_occurrence = find_last_occurrence(nums, target)

        return [first_occurrence, last_occurrence]