在升序数组中找到 target 的范围
要求
自然想到二分查找
- 查找下限
nums[mid]<target left=mid;
else right=mid; - 查找上限
nums[mid]>target right = mid
else left = mid
class Solution
{
public:
vector<int> searchRange(vector<int>& nums, int target)
{
vector<int> res(2, -1);
int size = nums.size();
if (size == 0) return res;
int left = 0, right = size - 1;
while (right > left)
{
int mid = (left + right) / 2;
if (nums[mid] < target)
left = mid + 1;
else
right = mid;
}
if (nums[left] == target)
res[0] = left;
else
return res;
left = 0;
right = size - 1;
while (left < right)
{
int mid = (left + right + 1) / 2;
if (nums[mid] > target)
right = mid - 1;
else
left = mid;
}
res[1] = right;
return res;
}
};
✔ Accepted
✔ 88/88 cases passed (8 ms)
✔ Your runtime beats 92.89 % of cpp submissions
✔ Your memory usage beats 76.77 % of cpp submissions (10.3 MB)
