LeetCode 剑指 Offer 53 - I. 在排序数组中查找数字 I
题目描述
给定一个排序数组
nums和一个目标值target，请你在数组中查找目标值target的出现次数。如果target不存在于数组中，则返回 0。
示例 1：
输入：
nums = [5, 7, 7, 8, 8, 10],target = 8
输出：2
解释：8在数组中出现了两次。
示例 2：
输入：
nums = [5, 7, 7, 8, 8, 10],target = 6
输出：0
解释：6在数组中不存在。
提示：
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
题意分析
统计非递减数组中
target出现了多少次，不存在时返回0。数组允许为空，相同值在排序后必然形成一段连续区间，因此次数等于这一段的长度。找到任意一个匹配值后再向两侧逐个扩展，最坏仍需扫描整个数组。可以直接用两次边界二分找到目标区间的开始与结束，在对数时间内计算数量，不需要逐个访问重复值。
解法：二分查找左右边界
核心思路
[!blue]
lowerBound找到第一个大于等于目标的位置first，upperBound找到第一个严格大于目标的位置after。有序性保证[first, after)内的元素既不小于目标、又不大于目标，因此恰好全部等于目标，数量就是after - first。两次查找都使用
[left, right)，初始化为[0, n)。对相应判据，左边界之前的元素已经确定不满足，右边界及其之后的元素已经确定满足；未确定的部分留在中间继续二分。边界可以等于n，表示直到数组末尾都没有满足判据的元素。中点满足判据时，它可能已经是第一个满足的位置，也可能左侧还有更早的位置，因此令
right = mid；不满足时，依据有序性，中点及其左侧都可排除，令left = mid + 1。两端相遇时，不满足部分与满足部分的分界就已经确定。两次查找的差别只在相等情况：下界遇到等于目标的中点，应继续往左找；上界遇到等于目标的中点，还没有满足严格大于的要求，应继续往右找。因此两者分别使用
>=和>，不能找到相等值就提前返回。如果目标不存在，第一个大于等于目标的位置也就是第一个严格大于目标的位置，两边界相等，差值自然为
0。空数组也直接返回两个0；目标位于数组两侧之外时，边界同样能用0或n表示，无需额外访问边界处的元素。
解题步骤
- 对条件
nums[mid] >= target做边界二分，得到first。- 对条件
nums[mid] > target做同样的边界二分，得到after。- 每次都初始化
left = 0、right = n，只在left < right时继续。- 满足本次判据则令
right = mid，否则令left = mid + 1；最终返回相遇位置。- 两个查找结果相减，返回
after - first。
代码实现
class Solution {
public int search(int[] nums, int target) {
// 目标出现范围左闭右开，两端之差就是数量。
return upperBound(nums, target) - lowerBound(nums, target);
}
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) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private int upperBound(int[] nums, int target) {
int left = 0;
int right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
// upperBound 找第一个严格大于 target 的位置。
if (nums[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
func search(nums []int, target int) int {
// 目标出现范围左闭右开，两端之差就是数量。
return upperBound(nums, target) - lowerBound(nums, target)
}
func lowerBound(nums []int, target int) int {
left := 0
right := len(nums)
for left < right {
mid := left + (right-left)/2
if nums[mid] >= target {
right = mid
} else {
left = mid + 1
}
}
return left
}
func upperBound(nums []int, target int) int {
left := 0
right := len(nums)
for left < right {
mid := left + (right-left)/2
if nums[mid] > target {
right = mid
} else {
left = mid + 1
}
}
return left
}
复杂度分析
- 时间复杂度：$O(\log(n+1))$，两次二分只增加常数倍。
- 空间复杂度：$O(1)$，只使用常数个下标变量。
关键点总结
[!green]
- 不要找到一个目标后向两侧线性扩展；全为目标值时会退化为 $O(n)$。
lowerBound与upperBound的唯一关键差异是>=和>。- 半开区间允许返回
nums.length，因此「目标比所有元素大」也能自然处理。
易错点总结
[!yellow]
- 半开区间右端写成
n - 1：会漏掉末尾位置，也无法自然表示整个数组之后的边界。- 满足判据时写
right = mid - 1：中点可能就是第一个符合的位置，不能把这个边界候选排除。- 两次都使用同一个比较符：得到的是同一个边界，无法计算目标覆盖的区间长度。
- 返回差值时额外加一：
after已经位于目标区间之后，半开区间长度直接相减即可。- 把返回边界当成有效下标读取：它可能等于
n，本解法只用它们计算距离，不访问对应元素。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 35. 搜索插入位置 | 简单 | 下界查询可找第一次出现，本题还需求大于目标的第一个位置以得到右边界。 |
| 704. 二分查找 | 简单 | 普通二分找到任意相等位置即可，本题必须继续沿边界方向收缩。 |