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

## 題解

### Binary search find left and right bound

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        def binary_search_bound(bound: bool): # left bound: false, right bound: true
            left, right = 0, n - 1
            ans = -1

            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] == target:
                    ans = mid
                    if bound:
                        left = mid + 1
                    else:
                        right = mid - 1
                else:
                    if nums[mid] > target:
                        right = mid - 1
                    else:
                        left = mid + 1
            return ans
        
        left = binary_search_bound(False) # left bound
        if left == -1:
            return [-1,-1]
        right = binary_search_bound(True) # right bound
        return [left,right]