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

鲁迅曾说，笑傲江湖其实讲的就是最真实的人性，有些人明明做了坏事，却能装

出一副正义凛然的样子，有些人明明做了好事，却被人说成是坏人。这就是江

湖，这就是人性。如果你想不被人欺负，就要学会自强自立，不依赖别人。对于

程序员来说，笔试想要取得好成绩，多刷一点 LeetCode 也是应该的。

题意

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目

标值在数组中的开始位置和结束位置。

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

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

难度

中等

示例

输入：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 的元素，记录下它的位置，最后返回这两个位置即可。

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 的测试用例不够严谨；要么就是，暴力算法也并没有想象中那么差，不仅效率

高，代码还简单。

034.%E5%9C%A8%E6%8E%92%E5%BA%8F%E6%95%B0%E7%BB%84%E4%B8%AD%E

6%9F%A5%E6%89%BE%E5%85%83%E7%B4%A0%E7%9A%84%E7%AC%AC%E4%B8%

80%E4%B8%AA%E5%92%8C%E6%9C%80%E5%90%8E%E4%B8%80%E4%B8%AA%E4

%BD%8D%E7%BD%AE-20240614082151.png

分析 2

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

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

一开始，我们可能会想到直接查找数组中是否存在这个 target 值，然后再向左右扩展，

可是这个思路如果遇到 nums = [5,5,5,5,5], target = 5 的情况，就需要遍历整个数组！

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

怎么办呢？

如果用 C++来解题的话，可以利用它自带的两个二分查找函数——lower_bound()和

upper_bound()，lower_bound()会返回大于或者等于 target 的第一个元素的位置，

upper_bound()会返回大于 target 的第一个元素。

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

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

是最后一个。

034.%E5%9C%A8%E6%8E%92%E5%BA%8F%E6%95%B0%E7%BB%84%E4%B8%AD%E

6%9F%A5%E6%89%BE%E5%85%83%E7%B4%A0%E7%9A%84%E7%AC%AC%E4%B8%

80%E4%B8%AA%E5%92%8C%E6%9C%80%E5%90%8E%E4%B8%80%E4%B8%AA%E4

%BD%8D%E7%BD%AE-20240614085426.png

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

辅助方法 findFirstPosition：

// 查找目标值的第一个位置

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：

// 查找目标值的最后一个位置

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 继续查找。

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

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;

 }

}

来看一下题解效率：

034.%E5%9C%A8%E6%8E%92%E5%BA%8F%E6%95%B0%E7%BB%84%E4%B8%AD%E

6%9F%A5%E6%89%BE%E5%85%83%E7%B4%A0%E7%9A%84%E7%AC%AC%E4%B8%

80%E4%B8%AA%E5%92%8C%E6%9C%80%E5%90%8E%E4%B8%80%E4%B8%AA%E4

%BD%8D%E7%BD%AE-20240614092553.png

总结

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

查找。

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

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

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

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

• 如果相等，返回 mid。

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

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

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

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

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;

}

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

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/