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

Solution

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)

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.