34. Find First and Last Position of Element in Sorted Array | LeetCode
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
class Solution
{
public:
vector<int> searchRange(vector<int> &A, int target)
{
int n = A.size();
int i = 0, j = n - 1;
vector<int> ret(2, -1);
if (n == 0)
return ret;
while (i < j)
{
int mid = (i + j) / 2;
if (A[mid] < target)
i = mid + 1;
else
j = mid;
}
if (A[i] != target)
return ret;
else
ret[0] = i;
j = n - 1;
while (i < j)
{
int mid = (i + j) / 2 + 1;
if (A[mid] > target)
j = mid - 1;
else
i = mid;
}
ret[1] = j;
return ret;
}
};
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.