[Algorithm] LeetCode 34. Find First and Last Position of Element in Sorted Array in Python

💡 LeetCode 34:

정렬된 배열에서 타겟이 등장하는 처음과 마지막 인덱스 찾기

🌱 코드 in Python

알고리즘: Binary Search

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if target not in nums:
            return [-1, -1]
        l = len(nums) - 1

        left, right = 0, l
        start, end = -1, -1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] >= target:
                start = mid
                right = mid - 1
            else:
                left = mid + 1

        end = start
        left = start + 1
        right = l
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] <= target:
                end = mid
                left = mid + 1
            else:
                right = mid - 1

        return [start, end]

이분 탐색 문제이지만 타겟을 찾았을 때 바로 종료하는 것이 아닌 가장 처음과 마지막을 찾아야 하는 문제였다.

여기서 어떻게 타겟을 찾았을 때 종료시키지 않고 더 왼쪽으로, 또는 더 오른쪽으로 탐색할 수 있지..? 하고 고민을 좀 했다..

아직도 어렵다 어려워..

아무튼!
코드 중간에서 start와 end가 갱신되어야 한다고 생각했고,
target을 찾아도 right를 하나 더 줄여서 더 왼쪽에 target이 있는지 찾았다.
반대의 경우에는 left를 하나 더 늘려서 더 오른쪽에 target이 있는지 찾았다.

🧠 기억하자

1. 갱신을 언제 해야 하는가!를 잘 생각해 보자.

LeetCode 34 바로가기