LeetCode 补充题 210. 有序数组中目标值的首个位置
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 34. 在排序数组中查找元素的第一个和最后一个位置
LeetCode 原题返回目标值的首、末位置；本文仅返回首次出现的位置，不存在时返回 -1。
:::
给定非降序整数数组
nums和目标值target，返回目标值第一次出现的下标，不存在时返回-1。
示例 1：
输入：
nums = [1,2,2,3], target = 2
输出：1
提示：
- 允许空数组。
- 数组元素和目标值为
32位整数。
题意分析
目标可能重复出现，普通二分遇到相等就返回不能保证最早位置。改为寻找小于 target 与不小于 target 两部分的分界，再检查该位置是否确实等于目标。
解法：左边界二分
核心思路
[!blue]
搜索目标不是任意一个 target，而是“第一个不小于 target 的位置”。升序数组中，小于 target 的位置都在左侧，不小于的都在右侧，因此可以找这个分界。
代码维护左闭右开的
[left,right)。中点太小就令left=mid+1；中点已不小于目标时，它自己仍可能是最早位置，所以令right=mid。结束时的 left 允许等于数组长度，表示插在末尾。最后再判断是否越界以及该值是否恰好等于 target。二分找到了插入边界，并不代表目标一定存在。
解题步骤
- 设置左闭右开区间 [0,n)，循环直到左右边界相等。
- 中值小于目标时令 left=mid+1；否则令 right=mid，保留中点作为可能的左边界。
- 结束后先检查 left 是否越界，再检查 nums[left] 是否等于 target。
- 两项检查通过则返回 left，否则返回 -1。
代码实现
class Solution {
public int searchFirst(int[] nums, int target) {
int left = lowerBound(nums, target);
if (left == nums.length || nums[left] != target) {
return -1;
}
return left;
}
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 searchFirst(nums []int, target int) int {
left := lowerBound(nums, target)
if left == len(nums) || nums[left] != target {
return -1
}
return left
}
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]
用左闭右开的二分区间求第一个不小于目标的位置，再验证该位置没有越界且值等于目标。
易错点总结
[!yellow]
- 遇到相等仍继续向左收缩，不能直接返回 mid。
- 右边界为 n，配套更新是 right=mid，不是 mid-1。
- 结束位置可能等于 n，必须先检查越界再读取元素，空数组也由此处理。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 34. 在排序数组中查找元素的第一个和最后一个位置 | 中等 | 均可通过二分寻找目标值左边界；该题还查找最后出现的位置，本题只返回首个位置，不存在时返回 -1。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！