## Find First and Last Position of Element in Sorted Array

• Time:O(\log n)
• 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) / 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
``````