noodleProblems/
Find First and Last Position of Element in Sorted Array
#43

Find First and Last Position of Element in Sorted Array

AlgorithmmediumArrayBinary Search

Given an array nums sorted in non-decreasing order and a target, return the starting and ending index of target as a two-element array [first, last].

If target is not in the array, return [-1, -1]. Your algorithm must run in O(log n) time.

Example cases

  • range
    in nums = [5,7,7,8,8,10], target = 8
    out [3,4]
    8 spans indices 3 through 4.
  • absent
    in nums = [5,7,7,8,8,10], target = 6
    out [-1,-1]
  • empty
    in nums = [], target = 0
    out [-1,-1]

Constraints

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • nums is sorted in non-decreasing order.
  • -10^9 <= target <= 10^9
Saved
nums =
[5,7,7,8,8,10]
target =
8