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

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

처음에 그냥 문제 대충 읽고 첫번째 테.케보고 아 타겟이랑 같으면 idx번호 리턴하면 되겠구나 했는데...

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        out = []
        
        for i in range(len(nums)):
            if target in nums:
                if target == nums[i]:
                    out.append(i)
                
        if target not in nums:
            out.extend([-1,-1]) 
                    
        return out
                

실패한 테케 :
Input
[1]
1
Output
[0]
Expected
[0,0]

..

문제를 다시 보니
' find the starting and ending position'

넵..

사용된 알고리즘은 Binary Search 였다.

     left = 0
        right = len(nums) -1
        
        start = -1
        end = -1
        while left <= right: # 가장 왼쪽 찾기
            mid = (left + right) // 2
            
            if nums[mid] > target:
                right = mid -1
            elif nums[mid] < target:
                left = mid + 1
            elif nums[mid] == target: # 여기가 포인트 target이 나와도 기록 후 더 낮은 target 값을 찾도록 한다.
                start = mid
                right = mid - 1
        
        if start == -1: # target 값이 아에 없을 경우에는 종료.
            return [-1, -1]
        
        left = 0
        right = len(nums) -1
        
        while left <= right: # 가장 오른쪽 찾기
            mid = (left + right) // 2    
            if nums[mid] > target:
                right = mid -1
            elif nums[mid] < target:
                left = mid + 1
            elif nums[mid] == target: # 여기가 포인트 target이 나와도 기록 후 더 높은 target 값을 찾도록 한다.
                end = mid
                print('end', end)
                left = mid + 1
                
        return [start, end]

start 포인트와 end 포인트를 binary search를 이용하여 푸었다..
다음번에 복습이 필요한 문제이다.