Find First and Last Position of Element in Sorted Array

Problem Id: 34 Difficulty: Medium Tag: Array Tag: Binary Search


Intuition

We could use 2 binary search to get the biggest element which is smaller than target and the smallest element which is bigger than target.

Solution


class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if not nums:
            return [-1, -1]

        if nums[0] > target:
            return [-1, -1]
        elif nums[0] == target:
            start = 0
        else:
            lo, hi = 0, len(nums)
            while hi > lo + 1:
                mid = (lo + hi) // 2
                if nums[mid] >= target:
                    hi = mid
                else:
                    lo = mid
            start = hi

        if nums[-1] < target:
            return [-1, -1]
        elif nums[-1] == target:
            end = len(nums) - 1
        else:
            lo, hi = 0, len(nums)
            while hi > lo + 1:
                mid = (lo + hi) // 2
                if nums[mid] <= target:
                    lo = mid
                else:
                    hi = mid
            end = lo

        if end >= start:
            return [start, end]
        return [-1, -1]