34. Find First and Last Position of Element in Sorted Array
题意
logn时间内找到一个有序数组内值为target的区间。
思路
两次二分即可。
代码
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if (!nums.size()) return vector<int>{-1,-1};
vector<int> res;
int left = 0, right = nums.size()-1;
while (left <= right)
{
int mid = (left+right)>>1;
if (nums[mid] < target)
left = mid+1;
else
right = mid-1;
}
if (left == nums.size() || nums[left] != target) return vector<int>{-1,-1};
res.push_back(left);
left = 0, right = nums.size()-1;
while (left <= right)
{
int mid = (left+right)>>1;
if (nums[mid] <= target)
left = mid+1;
else
right = mid-1;
}
res.push_back(right);
return res;
}
};