34. 在排序数组中查找元素的第一个和最后一个位置
4 min
题目
解法：二分查找
思路
核心思想是使用二分查找的变体分别搜索左边界和右边界。当找到目标值时不立即返回，而是通过调整搜索区间来持续向边界方向收缩，从而定位到最左和最右的出现位置。
这种方法的正确性基于数组已排序的特性：对于左边界搜索，当 nums[mid] == target 时，所有小于 mid 的位置都不可能包含目标值（因为数组非递减），但可能存在相同值的更早出现，因此将 right 移动到 mid-1 可以确保找到最左边界而不会遗漏；同理，右边界搜索时移动 left 到 mid+1 可确保找到最右边界。
- Step 1: 初始化左右指针和结果变量 first、last 为 -1
- Step 2: 第一次二分查找左边界，当 nums[mid] == target 时记录 first 并令 right = mid - 1
- Step 3: 重置左右指针，第二次二分查找右边界，当 nums[mid] == target 时记录 last 并令 left = mid + 1
- Step 4: 返回 {first, last} 结果数组
复杂度
- 时间复杂度:
- 空间复杂度:
代码
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
int first = -1, last = -1;
// 找第一个
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
first = mid;
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
// 找最后一个
left = 0;
right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
int first = -1, last = -1;
// 找第一个
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
first = mid;
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
// 找最后一个
left = 0;
right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
last = mid;
left = mid + 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return {first, last};
}
};