Problem URL: Find first and last position of element in sorted array

We will first do a regular binary search to get the position of the target. Then we expand both ways to get the left and right position of the target and return that. If we can't find the target we return [-1, -1].

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

                while l >= 0:
                    if nums[l] != target:
                        break
                    l -= 1

                while r <= len(nums)-1:
                    if nums[r] != target:
                        break
                    r += 1

                return [l+1, r-1]

        return [-1, -1]

Time Complexity: O(log(n))
Space Complexity: O(1)