#34
中等
中频
二分查找在排序数组中查找元素的第一个和最后一个位置
这是一道围绕数组、排序展开的高频练习。建议先掌握「二分查找」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
数组
排序
题目分析
给你一个升序数组和目标值 target。
要求返回目标值在数组中第一次出现和最后一次出现的位置。如果不存在，就返回 [-1, -1]。
一句话概括：
不是只判断目标值在不在，而是要找到它连续区间的左右边界。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：分别做两次边界二分：一次找最左出现位置，一次找最右出现位置。
推荐代码
推荐解法：二分查找
时间复杂度： O(log n)
空间复杂度： O(1)
核心思路： 分别做两次边界二分：一次找最左出现位置，一次找最右出现位置。
class Solution {
public int[] searchRange(int[] nums, int target) {
return new int[] {findLeft(nums, target), findRight(nums, target)};
}
private int findLeft(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int answer = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid - 1;
} else {
left = mid + 1;
}
if (mid < nums.length && nums[mid] == target) {
answer = mid;
}
}
return answer;
}
private int findRight(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int answer = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
if (mid < nums.length && nums[mid] == target) {
answer = mid;
}
}
return answer;
}
}
结构化讲解
面试时怎么讲
开场思路
这题我会把它看成两个边界查找问题，而不是一个普通查找问题。
核心过程
- 第一次二分找最左位置：命中目标时继续向左压边界。
- 第二次二分找最右位置：命中目标时继续向右压边界。
- 两次二分结束后，分别得到左右边界候选值。
- 最后校验这两个位置是否有效，不存在就返回
[-1, -1]。
复杂度总结
时间复杂度 O(log n)，空间复杂度 O(1)。
面试补一句：边界二分最重要的不是模板，而是想清楚命中目标后边界该往哪边收。
核心思路
这题不是一次二分能解决的普通查找题，而是典型的边界定位题。真正要找的是目标值出现区间的左右边界，因此需要两次二分各司其职。
步骤讲解
1
第一次二分找最左边界
当 nums[mid] >= target 时收缩右边界，逼近目标值第一次出现的位置。
为什么这样做：只要中点已经达到目标，就还要继续往左看是否能更早出现。
对应代码提示：if (nums[mid] >= target) right = mid - 1;
2
第二次二分找最右边界
当 nums[mid] <= target 时收缩左边界，逼近目标值最后一次出现的位置。
为什么这样做：只要中点还是目标，就还可能在右边继续延伸。
对应代码提示：if (nums[mid] <= target) left = mid + 1;
3
最后验证边界是否真的命中目标
二分结束后，需要检查求出的索引是否越界以及对应值是否等于目标值。
为什么这样做：目标值可能根本不存在，不能直接把边界下标当答案。
对应代码提示：if (left >= nums.length || nums[left] != target) return new int[] {-1, -1};
易错点
试图用一次二分同时找左右边界
命中目标后就不知道该继续偏左还是偏右，逻辑会变得模糊。
正确理解：把问题拆成两次独立的边界二分。
边界二分后不校验结果
目标不存在时，返回的插入位置很可能不是合法答案。
正确理解：结束后一定校验索引和数值是否匹配目标。
更新区间时还保留 mid
容易造成死循环，尤其是边界问题更敏感。
正确理解：保持标准写法：
left = mid + 1 或 right = mid - 1。复杂度与适用判断
时间复杂度：O(log n)
空间复杂度：O(1)
比其他方案更好在哪里：比线性扫描左右扩展更快，也更能体现对二分边界问题的掌握。
适用判断：有序数组里只要题目出现“第一个/最后一个/最左/最右”，优先想到边界二分。
额外提醒
- “找到目标”不是终点，“继续逼近边界”才是关键。
动画演示
如果你还没完全看懂，可以展开动画演示。
二分查找动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
二分查找动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 输入排序数组和目标值，然后点击开始
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。