[LeetCode 풀이/python] 34. Find First and Last Position of Element in Sorted Array (medium)

문제 설명: 오름차순 정렬된 정수 배열 nums 이 주어졌을 때, 배열 안에서 주어진 target 값이 등장하는 처음과 마지막 위치를 찾으시오. 만약 target 값이 배열 안에 존재하지 않으면, [-1, -1] 을 리턴하시오.

+ 추가: 시간 복잡도 O(log n) 의 알고리즘을 작성하시오

 

(Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

Follow up: Could you write an algorithm with O(log n) runtime complexity?)

 

예시 1)

입력: nums = [5,7,7,8,8,10], target = 8  -->  출력: [3,4]

 

예시 2)

입력: nums = [5,7,7,8,8,10], target = 6  -->  출력: [-1,-1]

 

예시 3)

입력: nums = [], target = 0  -->  출력: [-1,-1]

 

제한 조건:

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums 는 오름차순(non-decreasing) 정렬된 배열임
• -10^9 <= target <= 10^9

 

------ * ------ * ------ * ------

 

[풀이 1안]

• 접근법
  • 주어진 배열이 오름차순 정렬되어 있으므로, 이진 탐색(binary search) 알고리즘을 활용해 타겟 값이 배열 안에 존재하는지 & 인덱스 확인  -->  O(log n) 소요
    • 탐색 결과 존재하지 않으면 [-1, -1] 리턴
  • 탐색 결과 알아낸 타겟 값의 인덱스를 기준으로 앞뒤 인덱스의 값을 비교해가며 타겟 값의 경계를 확인

 

• 코드 구현

def searchRange(nums: List[int], target: int) -> List[int]:
    l, r = 0, len(nums)-1
    idx = -1
    
    while l <= r:
        mid = (l+r)//2
        if target < nums[mid]:
            r = mid-1
        elif target > nums[mid]:
            l = mid+1
        else:
            idx = mid
            break

    if idx == -1: return [-1, -1]
    else:
        s, e = idx, idx
        while (s > 0):
            if nums[s-1] == target: s -= 1
            else: break
        while (e < len(nums)-1):
            if nums[e+1] == target: e += 1
            else: break

    return [s,e]

 

• 결과
  • 이진 탐색을 통해 기준이 되는 인덱스를 찾은 뒤 start & end 인덱스 (경계) 를 찾아가는 과정이 linear 하긴 하지만 기본적으로 탐색 범위가 줄어든 상태이므로 전체 complexity 는 O(log n) 인 듯...?
  • 다른 풀이들을 살펴보니 start / end 인덱스 각각에 대해 이진 탐색을 해서 구하는 접근이 많다...!