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

중복되는 수가 존재하는 정렬된 리스트에서  target수가 존재하는 구간의 양 끝 인덱스를 출력하는 문제이다.

 

푸는 방법

1. 이진탐색으로 target을 찾는다. : def searchRange
2. 그 target으로부터 양쪽으로 순차적으로 탐색하여 찾는다. : def firstend

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        l = 0
        r = len(nums)-1
        def firstend(m): #target 구간 인덱스 구하기
            li = m
            ri = m
            while True:
                if li == -1 or nums[li] != target:
                    li += 1
                    break
                li -= 1
            while True:
                if ri == len(nums) or nums[ri] != target:
                    ri -= 1
                    break
                ri += 1
            return [li,ri]

        while l <= r: #target 이진탐색
            m = (l + r) // 2
            print(l,m,r)
            if nums[m] == target:
                return firstend(m)
            elif nums[m] > target:
                r = m - 1
            elif nums[m] < target:
                l = m + 1
        return [-1,-1]