034.在排序数组中查找元素的第一个和最后一个位置

作者：沉默王二
发布时间：2024-06-14T09:39:20.882+0800

鲁迅曾说，笑傲江湖其实讲的就是最真实的人性，有些人明明做了坏事，却能装出一副正义凛然的样子，有些人明明做了好事，却被人说成是坏人。这就是江湖，这就是人性。如果你想不被人欺负，就要学会自强自立，不依赖别人。对于程序员来说，笔试想要取得好成绩，多刷一点 LeetCode 也是应该的。

技术派阅读地址：https://paicoding.com/column/7/34

语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu

这道题可以说完全重写了，给出 1 道大家完全都能掌握的题解（利用二分查找）。

增加代码注释，这样大家更容易看懂并掌握题解；

增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；

增加手绘图，这样大家更容易理解解题思路；

增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；

增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；

图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。

另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

题意

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

难度

中等

示例

textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
输入：nums = [], target = 0
输出：[-1,-1]
### 分析 1

在排序数组中查找元素的第一个和最后一个位置，如果不考虑时间复杂度的话，会非常简单。

第一次遍历，从左到右找到第一个等于 target 的元素，记录下它的位置；第二次遍历，从右到左找到第一个等于 target 的元素，记录下它的位置，最后返回这两个位置即可。

textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
class Solution {
public int[] searchRange(int[] nums, int target) {
int lef = -1,rig = -1;
// 找第一个位置
for(int i = 0;i < nums.length;i++){
if(nums[i] == target){
lef = i;
break;
}
}
// 找最后一个位置
for(int i = nums.length - 1;i >= 0;i--){
if(nums[i] == target){
rig = i;
break;
}
}
return new int[]{lef,rig};
}
}

这样的速度也是出奇的快，直接击败 100% 的 Java 用户，这样的结果，只能证明，要么 LeetCode 的测试用例不够严谨；要么就是，暴力算法也并没有想象中那么差，不仅效率高，代码还简单。

分析 2

当然了，题目要求的时间复杂度为 O(log n)，那么我们还是需要使用二分查找的。

怎么去使用二分查找法呢？

一开始，我们可能会想到直接查找数组中是否存在这个target值，然后再向左右扩展，可是这个思路如果遇到nums = [5,5,5,5,5], target = 5的情况，就需要遍历整个数组！

这时候，时间复杂度就又变成了$O(n)$，而不是$O(\log{n})$。

怎么办呢？

如果用C++来解题的话，可以利用它自带的两个二分查找函数——lower_bound()和upper_bound()，lower_bound()会返回大于或者等于 target 的第一个元素的位置，upper_bound()会返回大于 target 的第一个元素。

但我们毕竟是 Java 选手，Java 有这样类似的方法吗？

我能想到的是Arrays.binarySearch()，但该方法只负责找到一个，并不区分是第一个还是最后一个。

那我们就需要自定义方法来模拟 lower_bound()和upper_bound()这两个方法了。

辅助方法 findFirstPosition：

textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
// 查找目标值的第一个位置
private int findFirstPosition(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 {
// 如果 mid 是第一个元素或者前一个元素不等于 target，mid 就是第一个位置
if (mid == 0 || nums[mid - 1] != target) {
return mid;
}
// 否则在左半部分继续查找
right = mid - 1;
}
}
return -1;
}

①、初始化左右指针 left 和 right。

②、当 left 小于等于 right 时，计算中间位置 mid。

③、如果中间值 nums[mid] 小于目标值 target，移动左指针 left 到 mid + 1。

④、如果中间值 nums[mid] 大于目标值 target，移动右指针 right 到 mid - 1。

⑤、如果中间值 nums[mid] 等于目标值 target：

检查 mid 是否为第一个元素或其前一个元素是否不等于目标值。如果是，则返回 mid。

否则，将右指针 right 移动到 mid - 1 继续查找。

假如输入是 nums = [5,7,7,8,8,10] 和 target = 8，我们来模拟一下 findFirstPosition 方法。

①、初始状态：left = 0, right = 5

②、第一次循环：

mid = (0 + 5) / 2 = 2

nums[mid] = nums[2] = 7, 小于 target = 8

更新 left = mid + 1 = 3，在右半部分

③、第二次循环：

mid = (3 + 5) / 2 = 4

nums[mid] = nums[4] = 8, 等于 target = 8

mid 不是第一个元素且 nums[mid - 1] = nums[3] = 8，继续向左查找(说明左侧还有符合要求的)

更新 right = mid - 1 = 3

④、第三次循环：

mid = (3 + 3) / 2 = 3

nums[mid] = nums[3] = 8, 等于 target = 8

mid 是第一个元素或者 nums[mid - 1] != target，即 nums[2] = 7 != 8

返回 mid = 3

辅助方法 findLastPosition：

textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
// 查找目标值的最后一个位置
private int findLastPosition(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 {
// 如果 mid 是最后一个元素或者后一个元素不等于 target，mid 就是最后一个位置
if (mid == nums.length - 1 || nums[mid + 1] != target) {
return mid;
}
// 否则在右半部分继续查找
left = mid + 1;
}
}
return -1;
}

①、初始化左右指针 left 和 right。

②、当 left 小于等于 right 时，计算中间位置 mid。

③、如果中间值 nums[mid] 小于目标值 target，移动左指针 left 到 mid + 1。

④、如果中间值 nums[mid] 大于目标值 target，移动右指针 right 到 mid - 1。

⑤、如果中间值 nums[mid] 等于目标值 target：

检查 mid 是否为最后一个元素或其后一个元素是否不等于目标值。如果是，则返回 mid。

否则，将左指针 left 移动到 mid + 1 继续查找。

最后，来调用两个辅助方法找到元素的第一个位置和最后一个位置。

textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] result = new int[2];
result[0] = findFirstPosition(nums, target);
result[1] = findLastPosition(nums, target);
return result;
}
}

来看一下题解效率：

总结

只要遇到要求时间复杂度为 O(log n)，那都是要使用二分查找法的，大家一定要学好二分查找。

其基本思想就是通过将查找范围每次缩小一半，从而快速定位到目标值。

第一步，初始化左右边界 left 和 right。

第二步，计算中间位置 mid。

第三步，比较 mid 位置的值与目标值：

如果相等，返回 mid。

如果小于目标值，更新 left 为 mid + 1。

如果大于目标值，更新 right 为 mid - 1。

第四步，重复上述步骤，直到 left 大于 right。

大家记住这个标准的模板：

textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
int binarySearch(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) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}

当然了，二分查找存在很多变种，比如说查找第一个大于等于目标值的位置：

textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
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;
}

多练习，多总结，掌握不是问题。

力扣链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/