LeetCode 34(Find First and Last Position of Element in Sorted Array)

1. 문제 링크

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

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

 

2. 문제 설명

• 오름차순으로 정렬된 array, nums가 주어졌을 때, 주어진 target value의 시작 위치와 끝 위치를 반환 
• 만약 target이 nums에 없다면, [-1,-1]을 반환
• O(log n) 시간복잡도가 되도록 짜야 할 것
• 예시1) nums=[5,7,7,8,8,10], target=8이면, 8은 3번째 index부터 4번째 index까지 위치하므로 [3,4]를 반환
• 예시2) nums=[5,7,7,8,8,10], target=6이면, 6은 nums에서 찾을 수 없으므로, [-1,-1]을 반환

3. 처음 풀이

• 문제를 보고 바로 생각이 들었던 풀이는,
  
  • 우선 이진 트리로, 처음 index와 target이 같아지는 값을 찾은 뒤, 
    • 해당 index의 앞, 뒤로 각각 while문을 돌려서 최소 index와 최대 index를 찾아서 반환
• runtime 77%정도로 무난히 통과하였음
  • 다만 while문을 돌리는 것 때문에 log n + k 느낌이다

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:

        l = 0 
        r = len(nums)

        index = -1 

        while l < r:
            m = (l+r)//2
            if nums[m] == target:
                index = m 
                break
            elif nums[m] > target:
                r = m
            elif nums[m] < target:
                l = m+1

        if index == -1:
            return [-1,-1]
        
        i = m
        while (nums[i] == target and i >=0): 
            result_min = i
            i -= 1 

        i = m
        while (i < len(nums) and nums[i] == target): 
            result_max = i
            i += 1

        return [result_min, result_max]

 

4. 다른 풀이

• 아예 binary_search라는 함수를 만들어두고, 
  • 그 안의 함수는 위 풀이와 유사하나
  • 왼쪽 index를 탐색할 때는, r = m-1로, 오른쪽을 탐색할 때는 l = m+1로 셋팅을 해둔다
    • 왼쪽을 탐색 시, r = m이 아니라 m-1로 하면서, 더 낮은 index를 찾도록 반복하는 것이고 
      • 만약 더 낮은 index가 없다면 그냥 index = mid가 됨
    • 오른쪽 탐색 시에도, 마찬가지로 m+1을 하면서 더 높은 index를 찾도록 반복하는 것
  • 이렇게 하면, 확실한 log n의 복잡도를 가지며, runtime 도 우수했다! 

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def binary_search(nums, target, left):
            low, high = 0, len(nums) - 1
            index = -1
            while low <= high:
                mid = (low + high) // 2
                if nums[mid] == target:
                    index = mid
                    if left:
                        high = mid - 1
                    else:
                        low = mid + 1
                elif nums[mid] < target:
                    low = mid + 1
                else:
                    high = mid - 1
            return index

        left_index = binary_search(nums, target, left=True)
        right_index = binary_search(nums, target, left=False)

        return [left_index, right_index]

 

5. 배운점

• 이진 탐색이 결국, 중간 값과의 비교를 통해 범위를 줄이는 과정인데,
• 만약 찾고자 하는 k가 여러개가 있다면, 양 끝값을 어떻게 업데이트 하면 좋을지 생각하게 된 문제!