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
题意分析
输入是一个已经按非递减顺序排好的整数数组和一个目标值，要求输出目标值在数组中出现了多少次；目标值不存在时输出
0。「已排序」这个前提带来一个直接推论：相等的元素必然挤在一起，构成一段连续区间。于是「出现次数」等价于「这段区间的长度」，问题从计数变成了定位两个端点。
约束里的信号很明确。数组长度可达 $10^5$，从头扫到尾的 $O(n)$ 做法虽然能过，但完全没有用上「有序」这个条件，出这道题的意图显然是考察对数级别的定位能力。元素取值范围到 $10^9$，接近
int边界，说明任何对目标值做加减再去搜索的取巧写法都有溢出风险。边界情况要提前想到：数组可能为空（长度为
0），目标值可能比所有元素都小或都大，也可能整个数组都等于目标值。这几种情况都必须落进同一套逻辑里，不应该靠特判打补丁。
解法：二分查找左右边界
核心思路
有序数组中的相同元素必然连续，因此出现次数可以转化为两个边界之差：
lowerBound：第一个大于等于target的位置；upperBound：第一个严格大于target的位置。等于
target的区间恰好是[lowerBound, upperBound)，答案就是upperBound - lowerBound。目标不存在时两个边界相同，差值自然为0；空数组也无需特判。两次搜索都使用半开区间
[left, right)。循环不变量是：left左侧都不满足当前判据，right及其右侧的实际元素都满足判据，答案仍在边界之间。判据在有序数组上具有单调性，循环结束时left == right，该位置就是第一个满足条件的下标。直接搜索「第一个大于
target」比搜索target + 1更稳妥，不依赖数值范围，也没有整数溢出风险。
解题步骤
- 在
[0, nums.length)中二分查找第一个nums[i] >= target的位置first。- 每轮取
mid = left + (right - left) / 2；满足判据时保留mid，令right = mid，否则令left = mid + 1。- 用相同骨架查找第一个
nums[i] > target的位置after。- 返回
after - first。例如
nums = [5, 7, 7, 8, 8, 10]、target = 8，两个边界分别为3和5，所以出现次数为2。若target = 6，两个边界都为1，结果为0。
代码实现
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)$，两次二分只增加常数倍。
- 空间复杂度：$O(1)$，只使用常数个下标变量。
关键点总结
- 不要找到一个目标后向两侧线性扩展；全为目标值时会退化为 $O(n)$。
lowerBound与upperBound的唯一关键差异是>=和>。- 半开区间允许返回
nums.length，因此「目标比所有元素大」也能自然处理。- 面试时先说清「找第一个满足单调判据的位置」，再写
right = mid与left = mid + 1。
易错点总结
- 把
right初始化为nums.length - 1：半开区间将无法表示末尾之后的合法边界。- 满足判据时写
right = mid - 1：mid可能就是第一个满足位置，会被错误排除。- 两个边界使用同一个比较符：对
[8, 8]会得到相同下标，错误返回0。- 用
target + 1求右边界：当target为整数上界时会溢出，应直接判断nums[mid] > target。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 34. 在排序数组中查找元素的第一个和最后一个位置 | 中等 | 要返回下标本身，且不存在时须给出 [-1, -1]
|
| 35. 搜索插入位置 | 简单 | 只需一次 lowerBound，重点是理解插入语义 |
| 278. 第一个错误的版本 | 简单 | 判据来自接口调用而非数组，还要控制调用次数 |
| 367. 有效的完全平方数 | 简单 | 在数值域上二分，需防平方溢出 |
| 540. 有序数组中的单一元素 | 中等 | 判据建立在下标奇偶配对上，不是简单的大小比较 |
| 704. 二分查找 | 简单 | 元素互不相同，只需定位一个位置，无边界区间概念 |
| LCR 068. 搜索插入位置 | 简单 | 与 35 同题换皮，可对照半开与闭区间两种模板 |
| LCR 070. 有序数组中的单一元素 | 中等 | 与 540 同题，重点在把配对性质翻译成单调判据 |
| 剑指 Offer 53 - II. 0～n-1中缺失的数字 | 简单 | 判据是「值是否等于下标」，找的是首个错位处 |
| 面试题 10.05. 稀疏数组搜索 | 简单 | 数组含空串需先横向探测，破坏了严格的单调性 |