LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置
题目描述
题意分析
在非递减排列的整数数组中，返回
target第一次和最后一次出现的下标，两端都包含在结果中。若目标不存在，返回[-1, -1]；数组允许为空。相同值在有序数组中必然连续，所以要找的是这一整段的左右边界。题目要求对数时间，不能先找到任意一个匹配位置，再逐个向两侧扫描，因为大量元素相同时，这样会退化为线性时间。
解法：两次边界二分
核心思路
[!blue]
先实现
lowerBound(x)，返回数组中第一个大于等于x的位置；如果所有元素都小于x，则返回数组长度n。有序性把数组分成前面的“小于x”和后面的“大于等于x”两段，二分要找的就是它们之间的分界。初始化
left = 0、right = n，在左闭右开的待检查范围[left, right)中取中点。若nums[mid] < x，中点及其左侧都不可能是答案，令left = mid + 1；否则中点可能已经是第一个符合的位置，也可能左侧还有更早的位置，令right = mid继续向左收缩。搜索期间，
left之前的值都已经确定小于x，right及其之后的值都已经确定大于等于x。当两者相遇，未确定的范围为空，它们所在的位置就是两段的分界。即使遇到相等值也不提前返回，才能定位最左端，而不是任意一次出现。第一次求
lowerBound(target)得到候选左端点。这个返回值也可能只是目标应该插入的位置，因此必须检查它没有越界，并且对应元素确实等于target；否则目标不存在。空数组也会直接得到n，无需访问数组元素。确认目标存在后，再求
lowerBound(target + 1)。由于数组元素都是整数，“大于等于target + 1”等价于“严格大于target”，所以这次得到的正好是目标连续区间之后的位置，减一就是最后一次出现的下标。若目标一直延伸到数组末尾，第二次会返回n，减一仍然正确。题目限定target在正负十亿之间，执行target + 1不会溢出。
解题步骤
- 调用
lowerBound(nums, target)，得到候选左端点left。- 先判断
left == n，再判断nums[left]是否等于目标；越界或不相等时返回[-1, -1]。- 再调用
lowerBound(nums, target + 1)，将结果减一作为右端点。- 两次查找都使用
[left, right)，循环条件为left < right；中点值较小时排除中点，否则向左寻找边界。- 返回包含两个端点的数组。
代码实现
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = lowerBound(nums, target);
// 边界二分返回插入位置，仍需确认目标真的存在。
if (left == nums.length || nums[left] != target) {
return new int[] {
-1,
-1
};
}
// 第二次得到目标区间后一位，减一才是最后出现位置。
return new int[] {
left,
lowerBound(nums, target + 1) - 1
};
}
private int lowerBound(int[] nums, int target) {
int left = 0;
int right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
func searchRange(nums []int, target int) []int {
left := lowerBound(nums, target)
// 边界二分返回插入位置，仍需确认目标真的存在。
if left == len(nums) || nums[left] != target {
return []int{
-1,
-1,
}
}
// 第二次得到目标区间后一位，减一才是最后出现位置。
return []int{
left,
lowerBound(nums, target+1) - 1,
}
}
func lowerBound(nums []int, target int) int {
left, right := 0, len(nums)
for left < right {
mid := left + (right-left)/2
if nums[mid] < target {
left = mid + 1
} else {
right = mid
}
}
return left
}
复杂度分析
- 时间复杂度：$O(\log n)$，两次二分查找不改变量级。
- 空间复杂度：$O(1)$。
关键点总结
[!green]
lowerBound返回第一个大于等于目标的位置，也可能返回n。nums[mid] == target时仍收缩右边界，才能继续寻找最左位置。- 本题约束保证
target + 1不溢出；它代表第一个严格大于target的边界。
易错点总结
[!yellow]
- 未校验左端点是否越界、是否等于目标，会把不存在的目标误判为存在。
- 左闭右开区间应初始化
right = n，循环条件是left < right。- 找右边界后忘记减一，会返回目标区间右侧的位置。
- 将比较条件写成
nums[mid] <= target，会把lowerBound变成上边界查找。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 35. 搜索插入位置 | 简单 | 下界查询可找第一次出现，本题还需求大于目标的第一个位置以得到右边界。 |
| 704. 二分查找 | 简单 | 普通二分找到任意相等位置即可，本题必须继续沿边界方向收缩。 |
| 补充题 210. 有序数组中目标值的首个位置 | 简单 | 都二分寻找目标的左边界；补充题只返回首个位置，无需再求右边界。 |
| 69. x 的平方根 | 简单 | 在有序或具有单调判定的区间进行边界二分；本题定位等于目标值的左右边界，该题以平方是否超过输入作为判定。 |
| 367. 有效的完全平方数 | 简单 | 在有序或具有单调判定的区间进行边界二分；本题定位等于目标值的左右边界，该题检查平方根边界是否精确命中。 |