LeetCodeSolutions
Advertisement

34. Find First and Last Position of Element in Sorted Array 👍

  • Time: $O(\log n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
 public:
  vector<int> searchRange(vector<int>& nums, int target) {
    const int l = ranges::lower_bound(nums, target) - nums.begin();
    if (l == nums.size() || nums[l] != target)
      return {-1, -1};
    const int r = ranges::upper_bound(nums, target) - nums.begin() - 1;
    return {l, r};
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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};
  }

  private int firstGreaterEqual(int[] A, int target) {
    int l = 0;
    int r = A.length;
    while (l < r) {
      final int m = (l + r) / 2;
      if (A[m] >= target)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }
}

1
2
3
4
5
6
7
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

var searchRange = function(nums, target) {
  const bound = (first) => {
    let l = 0, r = nums.length - 1, ans = -1;
    while (l <= r) {
      const m = Math.floor((l + r) / 2);
      if (nums[m] === target) {
        ans = m;
        if (first) r = m - 1;
        else l = m + 1;
      }
      else if (nums[m] < target) l = m + 1;
      else r = m - 1;
    }
    return ans;
  };
  return [bound(true), bound(false)];
};
Advertisement