34. Find First and Last Position of Element in Sorted Array
/*
* @lc app=leetcode id=34 lang=cpp
*
* [34] Find First and Last Position of Element in Sorted Array
*
* https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/
*
* algorithms
* Medium (45.48%)
* Likes: 21764
* Dislikes: 573
* Total Accepted: 2.6M
* Total Submissions: 5.7M
* Testcase Example: '[5,7,7,8,8,10]\n8'
*
* 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
*
*
*/
// @lc code=start
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target)
{
int n = nums.size();
vector<int> res(2, -1);
int left = 0, right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
if (right == n || nums[right] != target) {
return res;
}
res[0] = right;
right = n;
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;
}
};
// @lc code=end
- T:
- S: