Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

Constraints:

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums is a non-decreasing array.
• -10^9 <= target <= 10^9

We want to find two positions, first_pos and last_pos of the target in nums.

For the first_pos, we want to find the leftmost target. So we will do binary search on nums, and whenever we find target, we search for its left side to see whether there is another target on the left while keeping track of the leftmost seen first_pos.

Similarly, we want to find the rightmost target in nums to be last_pos. So when we see a target, we search for its right side and record the last_pos = current index. If the current element is not target, then ordinary binary search will lead us to the correct searching side.

1def searchRange(self, nums, target):
2    left, right = 0, len(nums)-1
3    first_pos, last_pos = -1, -1
4    
5    # find first pos
6    while left <= right:
7      mid = (left + right) // 2
8      if nums[mid] == target:
9          first_pos = mid
10          right = mid - 1
11      elif nums[mid] > target:
12          right = mid - 1
13      else:
14          left = mid + 1
15    
16    #find last pos
17    left, right = 0, len(nums)-1
18    while left <= right:
19      mid = (left + right) // 2
20      if nums[mid] == target:
21          last_pos = mid
22          left = mid+1
23      elif nums[mid] > target:
24          right = mid - 1
25      else:
26          left = mid + 1
27    return (first_pos, last_pos)

Solution Implementation