Find First and Last Position of Element in Sorted Array
这道题表面上看起来并不复杂： 给定一个有序数组和一个目标值 target，要求你找出它在数组中第一次出现的位置和最后一次出现的位置。
如果目标值不存在，就返回：
[-1, -1]
很多人第一次做这题时，都会想到先普通二分找到任意一个 target，然后再向左、向右扩展去找边界。这个思路当然可以做出来，但它并不是题目最想考察的方式。因为题目明确要求时间复杂度为：
O(log n)
而一旦你在找到目标之后再线性扩展，就有可能退化成 O(n)。
所以这道题真正想考的是：
如何用二分查找，分别找到目标值的左边界和右边界。
你给出的这份 Java 代码，就是这道题非常标准的一种写法： 通过写两个二分函数，分别查找第一个位置和最后一个位置。
本文就结合这段代码，系统地讲一下这道题的思路。
题目介绍
给定一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。
请你找出 target 在数组中的开始位置和结束位置，并返回一个长度为 2 的数组。
例如：
-
如果
target = 8，而数组中8出现的位置是下标3到4 -
那么就返回：
[3, 4]
如果数组中不存在这个目标值，就返回：
[-1, -1]
这道题的难点在于：
-
数组是有序的
-
目标值可能出现多次
-
要在
O(log n)时间内找到左右边界
这说明我们不能只用一次普通二分，而是要把“找边界”这件事单独拆开处理。
示例
示例 1
输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]
因为 8 在数组中第一次出现的位置是 3，最后一次出现的位置是 4。
示例 2
输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]
因为数组中不存在 6，所以返回 [-1,-1]。
示例 3
输入：nums = [], target = 0 输出：[-1,-1]
空数组中当然找不到任何元素。
最直接的想法为什么不够好？
一个很自然的想法是：
-
先普通二分找到任意一个
target -
再从这个位置向左扫描，找到第一个
target -
再向右扫描，找到最后一个
target
这个方法写起来不难，但问题在于：
如果数组里全是目标值，比如：
[8,8,8,8,8,8,8]
那么普通二分找到中间某个位置后，再向两边扩展，最坏情况还是要扫描整个数组。
这样时间复杂度就会退化成：
O(n)
而题目要求的是：
O(log n)
所以这道题真正的正确解法，应该是：
用二分查找左边界，再用二分查找右边界。
核心思路
因为数组是有序的，所以相同的元素一定是连续出现的。
这意味着：
-
第一个目标值的位置，本质上是“最左边那个等于
target的下标” -
最后一个目标值的位置，本质上是“最右边那个等于
target的下标”
所以这道题可以拆成两个子问题：
-
如何找第一个等于
target的位置 -
如何找最后一个等于
target的位置
这两个问题都可以用二分查找完成。
Java 代码
下面是你给出的代码，我这里保留原始逻辑，并加上注释：
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] result = new int[2];
result[0] = findfirstpostion(nums, target);
result[1] = findlastpostion(nums, target);
return result;
}
private int findfirstpostion(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else if (nums[mid] > target) right = mid - 1;
else {
// 当前值等于 target，还要继续判断它是不是最左边那个
if (mid == 0 || nums[mid - 1] != target) return mid;
right = mid - 1;
}
}
return -1;
}
private int findlastpostion(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else if (nums[mid] > target) right = mid - 1;
else {
// 当前值等于 target，还要继续判断它是不是最右边那个
if (mid == nums.length - 1 || nums[mid + 1] != target) return mid;
left = mid + 1;
}
}
return -1;
}
}
代码拆解
这段代码的整体结构很清晰：
-
主函数
searchRange负责调用两个边界查找函数 -
findfirstpostion负责查找左边界 -
findlastpostion负责查找右边界
真正值得理解的地方，是这两个二分函数到底和普通二分有什么不同。
1. 主函数为什么要分成两个查找？
result[0] = findfirstpostion(nums, target);
result[1] = findlastpostion(nums, target);
因为“第一个位置”和“最后一个位置”虽然都和 target 有关，但它们本质上是两个不同的问题。
如果强行写在一个二分里，会让逻辑变得很乱。 而拆成两个函数之后，每个函数只专注于一个目标，思路会更清楚，也更容易调试。
这是写二分题时一个非常常见的技巧：
不要害怕写两个二分。
很多边界类问题，本来就应该拆成两个方向去做。
2. 为什么 findfirstpostion 找到 target 后还不立刻结束？
else {
if (mid == 0 || nums[mid - 1] != target) return mid;
right = mid - 1;
}
这正是“找左边界”和“普通二分”的最大区别。
普通二分一旦找到目标值，就直接返回，因为题目只要求找到任意一个位置。 但这道题要求的是：
最左边那个位置
所以即使当前 nums[mid] == target，我们也不能立刻结束，而是还要继续判断：
-
如果
mid == 0，说明它已经是数组最左边 -
或者
nums[mid - 1] != target，说明它左边那个数不是目标值 -
只有这两种情况，当前
mid才是真正的第一个位置
否则，说明左边还存在目标值，那就要继续往左边缩小范围：
right = mid - 1;
这一步非常关键，它体现了边界二分的核心思想：
找到目标值还不够，要继续逼近边界。
3. 为什么 findlastpostion 的逻辑正好相反？
else {
if (mid == nums.length - 1 || nums[mid + 1] != target) return mid;
left = mid + 1;
}
这个函数要找的是最右边那个位置，所以逻辑和左边界查找是对称的。
当前 nums[mid] == target 时：
-
如果
mid == nums.length - 1，说明它已经在最右边 -
或者
nums[mid + 1] != target，说明它右边那个数不是目标值 -
这时当前
mid才是真正的最后一个位置
否则，说明右边还有目标值，所以要继续向右收缩：
left = mid + 1;
所以这两个函数本质上就是：
-
左边界查找：命中后继续往左压缩
-
右边界查找：命中后继续往右压缩
4. 为什么二分中点写成这样？
int mid = left + (right - left) / 2;
这是一种更稳妥的二分写法。
相比直接写：
int mid = (left + right) / 2;
这种写法可以避免在某些极端情况下整数溢出。
虽然在 LeetCode 这题里不一定真的会溢出，但这是写二分时非常推荐养成的习惯。
手动模拟一遍：找左边界
我们用经典样例来走一遍：
nums = [5,7,7,8,8,10], target = 8
第一次
-
left = 0 -
right = 5 -
mid = 2 -
nums[mid] = 7
因为：
7 < 8
所以目标值一定在右边：
left = mid + 1 = 3
第二次
-
left = 3 -
right = 5 -
mid = 4 -
nums[mid] = 8
这次命中了目标值，但不能直接返回。 还要看它是不是最左边那个：
-
nums[mid - 1] = nums[3] = 8
说明左边还有 8，所以当前 mid = 4 不是左边界。 继续往左找：
right = mid - 1 = 3
第三次
-
left = 3 -
right = 3 -
mid = 3 -
nums[mid] = 8
再次命中目标值。 这次检查左边：
-
nums[mid - 1] = nums[2] = 7 -
不等于
8
所以当前 mid = 3 就是第一个位置。
返回：
3
手动模拟一遍：找右边界
还是同样的例子：
nums = [5,7,7,8,8,10], target = 8
第一次
-
left = 0 -
right = 5 -
mid = 2 -
nums[mid] = 7
因为：
7 < 8
所以往右找：
left = 3
第二次
-
left = 3 -
right = 5 -
mid = 4 -
nums[mid] = 8
命中目标值，但还要检查是不是最右边那个。
-
nums[mid + 1] = nums[5] = 10 -
不等于
8
所以当前 mid = 4 就已经是最后一个位置。
返回：
4
最终结果就是：
[3, 4]
为什么这个算法一定正确？
因为数组有序，所以所有等于 target 的元素一定形成一个连续区间。
而二分查找最擅长做的事情，就是不断缩小搜索区间。
对于左边界查找：
-
如果
nums[mid] < target，左边都不可能是答案 -
如果
nums[mid] > target，右边都不可能是答案 -
如果
nums[mid] == target，当前可能是答案，但左边也可能还有答案，所以继续往左找
对于右边界查找：
逻辑完全类似，只不过命中后要继续往右找。
所以每一次循环都在正确地排除不可能区间，最终一定能收敛到正确边界。
复杂度分析
时间复杂度
主函数中调用了两次二分查找：
-
一次找左边界
-
一次找右边界
每次二分的时间复杂度都是：
O(log n)
所以总时间复杂度仍然是：
O(log n)
因为常数 2 可以忽略。
空间复杂度
只使用了常数级别的额外变量，所以空间复杂度是：
O(1)
这道题真正想考什么？
这道题表面上是在找下标范围，但本质上考察的是：
第一，是否真正理解“边界二分”
很多人学了普通二分之后，会觉得只要命中目标值就该返回。 但这道题会逼着你意识到：
有些二分题的目标不是“找值”，而是“找边界”。
这时候命中目标值只是中间状态，不是终点。
第二，是否能把一个问题拆成两个更清晰的问题
这道题最容易写乱的地方，就是想在一个二分里同时找左右边界。 实际上，拆成两个方向分别处理，反而更清晰、更稳定。
这也是写算法题时很重要的一种思维方式：
复杂问题拆成两个简单问题。
和普通二分查找有什么区别？
普通二分查找中：
-
只要
nums[mid] == target，就立即返回
而这道题中：
-
即使
nums[mid] == target，也不能立即结束 -
还要继续确认它是不是最左边或者最右边那个
所以它和普通二分最大的区别就在于：
命中目标后，不是结束，而是继续向边界逼近。
这就是“边界二分”的精髓。
总结
这道题的核心思想可以概括成一句话：
分别用两次二分查找，找到目标值在有序数组中的最左边界和最右边界。
具体做法就是：
-
写一个函数查找第一个等于
target的位置 -
写一个函数查找最后一个等于
target的位置 -
在二分中命中目标值后，不要立刻返回，而是继续向边界方向收缩
-
最终把两个结果组成数组返回
这样就能在：
O(log n)
的时间复杂度内完成查找。
这是一道非常经典、也非常值得反复理解的二分边界题。 因为它会让你真正意识到：二分查找不只是“找某个值在不在”，更重要的是学会利用二分去定位各种临界位置、边界位置和最左最右的满足条件点。
把这道题真正吃透之后，再去看：
-
搜索插入位置
-
查找旋转数组中的最小值
-
寻找第一个错误版本
-
找到峰值元素
这些二分边界题时，你会明显更容易抓住套路。
