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

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

 

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # O (log n) 이므로, bst 로 ..
        # bst 로 우선 target 이 있는지 없는지 찾고, 
        #   있으면 idx 반환, 없으면 -1 
        # 있으면, 좌우로 움직이면서, 시작, 끝 찾고
        def binary_search(l, r):
            while l<=r:
                mid = (l+r)//2

                if nums[mid] == target:
                    return mid
                
                if nums[mid] < target:
                    l = mid + 1
                else: # target < nums[mid]
                    r = mid -1
            return -1
        
        def find_start_leftside(l, r):
            while l<=r:
                mid = (l+r)//2
                if nums[mid] == target:
                    r = mid-1  # 왼쪽으로 계속 이동
                elif nums[mid] < target:
                    l = mid + 1
                else: 
                    r = mid -1
            return l

        def find_end_rightside(l, r):
            while l<=r:
                mid = (l+r)//2
                if nums[mid] == target:
                    l = mid + 1 # 오른쪽으로 계속 이동 
                elif nums[mid] < target:
                    l = mid + 1
                else: 
                    r = mid - 1
            # while 종료되면
            # r < l 이 되므로
            # r 이 타겟의 위치고,
            # l은 타겟보다 큰 첫번째 위치
            return r

        idx = binary_search(0, len(nums)-1)

        if idx == -1:
            return [-1, -1]
        else:
            start = find_start_leftside(0, idx)
            end = find_end_rightside(idx, len(nums)-1)
            return [start, end]