[LeetCode]Find First and Last Position of Element in Sorted Array

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Find First and Last Position of Element in Sorted Array - LeetCode

 

문제 분석

오름차순으로 정렬되어 있고 숫자가 중복으로 등장하는 리스트에서 target 값을 찾습니다. 다만 target 값이 여러개인 경우 가장 작은 인덱스와 큰 인덱스를 찾아야 합니다.

 

처음 시도한 답안 O(log n)

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # https://velog.io/@jungbumwoo/leetcode-34.-Find-First-and-Last-Position-of-Element-in-Sorted-Array
        
        left = 0
        right = len(nums)-1

        start = -1
        end = -1
        while left <= right: # 가장 왼쪽의 target 찾는 이분 탐색
            mid = (left+right) // 2

            if nums[mid] == target:
                start = mid
                # 이미 찾은 target에서 왼쪽으로 더 같은 숫자가 있는지 확인하기 위해 right를 옮김
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        if start == -1:
            return [-1, -1]

        left = 0
        right = len(nums)-1
        while left <= right: # 가장 오른쪽의 target 찾는 이분 탐색
            mid = (left+right) // 2

            if nums[mid] == target:
                end = mid
                # 이미 찾은 target에서 오른쪽으로 더 같은 숫자가 있는지 확인하기 위해 left를 옮김
                left = mid + 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return [start, end]

접근 방법

1. 마찬가지로 기본 알고리즘은 이분 탐색을 활용합니다.
2. 먼저, 가장 왼쪽의 target 값을 찾는 이분 탐색을 진행합니다.
   1. 일반적인 이분 탐색과 한가지 다른 점은, target을 찾은 경우에 right를 mid-1로 설정하여 왼쪽에 동일한 숫자가 있는지 확인합니다.
3. 찾지 못했다면 [-1, -1]을 return 합니다.
4. 두번째로, 가장 오른쪽의 target 값을 찾는 이분 탐색을 진행합니다.
   1. 마찬가지로, target을 찾은 경우에 left를 mid+1로 설정하여 오른쪽에 동일한 숫자가 있는지 확인합니다.
5. 가장 왼쪽에 위치한 start 가장 오른쪽에 위치한 end를 return 합니다.

이 문제의 경우에는 이분 탐색을 활용한다는 것 까지는 유추할 수 있었습니다. 하지만 가장 왼쪽과 오른쪽에 위치하는 target을 구하기 위해서 반복문 내에서 여러가지 조건을 추가해가면서 구현을 시도했으나 계속해서 추가되는 예외케이스로 인해 솔루션을 참고하게 되었습니다.

 

가장 명쾌한 솔루션은 이분 탐색을 총 2번 진행하는 방법입니다. 첫번째는 가장 왼쪽의 target을 찾는 이분 탐색, 두번째는 가장 오른쪽에 위치한 target을 찾는 이분 탐색입니다.