# 34. 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`

``````class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int idx = search(nums, 0, nums.size() - 1, target);
if (idx == -1) return {-1, -1};
int left = idx, right = idx;
while (left > 0 && nums[left - 1] == nums[idx]) --left;
while (right < nums.size() - 1 && nums[right + 1] == nums[idx]) ++right;
return {left, right};
}
int search(vector<int>& nums, int left, int right, int target) {
if (left > right) return -1;
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target) return search(nums, mid + 1, right, target);
else return search(nums, left, mid - 1, target);
}
};
``````

``````class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> res(2, -1);
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else right = mid;
}
if (right == nums.size() || nums[right] != target) return res;
res[0] = right;
right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) left = mid + 1;
else right = mid;
}
res[1] = right - 1;
return res;
}
};
``````

``````class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int start = firstGreaterEqual(nums, target);
if (start == nums.size() || nums[start] != target) return {-1, -1};
return {start, firstGreaterEqual(nums, target + 1) - 1};
}
int firstGreaterEqual(vector<int>& nums, int target) {
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else right = mid;
}
return right;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/34

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/discuss/14699/Clean-iterative-solution-with-two-binary-searches-(with-explanation)

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/discuss/14701/A-very-simple-Java-solution-with-only-one-binary-search-algorithm

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation