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

Example1

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example2

Input: nums = [], target = 0
Output: [-1,-1]

조건

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums is a non-decreasing array.
-109 <= target <= 109

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        
        le , ri = 0, len(nums) -1
        left = -1
        while le <= ri:
            mid = (le + ri) // 2
            if nums[mid] < target:
                le = mid + 1
            elif nums[mid] > target:
                ri = mid - 1
            elif nums[mid] == target:
                left = mid
                ri = mid -1 
        le , ri = 0, len(nums) -1
        right = -1
        
        while le <= ri:
            mid = (le + ri) // 2
            if nums[mid] < target:
                le = mid + 1
            elif nums[mid] > target:
                ri =  mid - 1
            elif nums[mid] == target:
                right = mid
                le = mid + 1
                
        return [left, right]

Related Topics - Binary Search가 있어서 이진트리로 해보았습니다.
예시로 Example 1기준으로 하면

le ri mid  nums[mid]    left
0  5   2       7         -1
3  5   4       8          4
3  3   3       8          3
3  2

le ri mid  nums[mid]    right
0  5   2      7           -1
3  5   4      8            4
5  5   5     10            4
5  4

하여 [3,4] 출력