Find First and Last Position of Element in Sorted Array

Solution

Binary Search

Complexity

time: $O(\log n)$
space: $O(1)$

def lower_bound(nums: List[int], target: int) -> List[int]:
    n = len(nums)
    lo, hi = 0, n-1
    while lo <= hi:
        mid = (lo + hi) // 2
        # commented part is for upper bound
        # if nums[mid] > target:
        #     hi = mid - 1
        # else:
        #     lo = mid + 1
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return lo

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        left = lower_bound(nums, target)
        if left > n-1 or nums[left] != target:
            return [-1, -1]
        right = lower_bound(nums, target+1) - 1
        return [left, right]

Expand from Middle

not recommended.

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        if n == 0:
            return [-1, -1]
        lo, hi = 0, n-1
        mid = 0
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                break
            elif nums[mid] > target:
                hi = mid - 1
            else:
                lo = mid + 1
        
        if nums[mid] != target:
            return [-1, -1]
        # expand from middle
        left = right = mid
        while left > 0 and nums[left-1] == nums[left]:
            left -= 1
        while right < n-1 and nums[right] == nums[right+1]:
            right += 1
        return [left, right]