Find First and Last Position of Element in Sorted Array | Easy Approach

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 <= 105
• -109 <= nums[i] <= 109
• nums is a non-decreasing array.
• -109 <= target <= 109

Find First and Last Position of Element in Sorted Array Solutions

✅Time: O(logn)
✅Space: O(1)

C++

 class Solution {
 public:
  vector<int> searchRange(vector<int>& nums, int target) {
    const int l = lower_bound(begin(nums), end(nums), target) - begin(nums);
    if (l == nums.size() || nums[l] != target)
      return {-1, -1};
    const int r = upper_bound(begin(nums), end(nums), target) - begin(nums) - 1;
    return {l, r};
  }
};

Java

 class Solution {
  public int[] searchRange(int[] nums, int target) {
    final int l = firstGreaterEqual(nums, target);
    if (l == nums.length || nums[l] != target)
      return new int[] {-1, -1};
    final int r = firstGreaterEqual(nums, target + 1) - 1;
    return new int[] {l, r};
  }

  // find the first index l s.t A[l] >= target
  // return A.length if can't find
  private int firstGreaterEqual(int[] A, int target) {
    int l = 0;
    int r = A.length;
    while (l < r) {
      final int m = l + (r - l) / 2;
      if (A[m] >= target)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }
}

Python

 class Solution:
  def searchRange(self, nums: List[int], target: int) -> List[int]:
    l = bisect_left(nums, target)
    if l == len(nums) or nums[l] != target:
      return -1, -1
    r = bisect_right(nums, target) - 1
    return l, r

Watch Tutorial

Checkout more Solutions here