[Coderust] Find First and Last Position of Element in Sorted Array

 

 

Problem

 

 

 

---

 

Solution

 

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # find target with binary search,
        # then expand until the number changes
        left = 0
        right = len(nums)-1
        start = -1
        end = -1
        
        while left <= right:
            mid = left + (right-left)//2
            if nums[mid] == target:
                start = mid
                end = mid
                break
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
                
        while 0 <= (start-1):
            if nums[start-1] == target:
                start -= 1
            else:
                break
        
        while 0 <= end and (end+1) < len(nums):
            if nums[end+1] == target:
                end += 1
            else:
                break
        
        return [start, end]

 

Time Complexity

O(log N)

 

 

Space Complexity

O(1)