# 「力扣」第 34 题：在排序数组中查找元素的第一个和最后一个位置（中等）
温馨提示：查找第一个元素和最后一个元素的代码不是背出来的，仔细分析就不难写出代码，关键是要认真。二分查找不是难点，也不是重点。
# 视频题解
这道题在 官方题解 (opens new window) 和 B 站 (opens new window) 可以收看视频讲解，选择快速播放，获得更好的观看体验。
# 题目描述
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
- 你可以设计并实现时间复杂度为
O(log n)的算法解决此问题吗？
示例 1：
输入: nums = [5, 7, 7, 8, 8, 10], target = 8
输出: [3, 4]
示例 2：
输入: nums = [5, 7, 7, 8, 8, 10], target = 6
输出: [-1, -1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
nums是一个非递减数组
# 思路分析
- 不可以找到
target以后，然后向两边扩散（线性查找），这样的话时间复杂度为，这里 是输入数组的长度； - 找
target第一次出现的位置和最后一次出现的位置的时候，都只能用「二分查找」才符合题目的意思，注意分类讨论，并且把分类讨论的结果合并。
参考代码：
public class Solution {
public int[] searchRange(int[] nums, int target) {
int len = nums.length;
if (len == 0) {
return new int[]{-1, -1};
}
int firstPosition = findFirstPosition(nums, target);
if (firstPosition == -1) {
return new int[]{-1, -1};
}
int lastPosition = findLastPosition(nums, target);
return new int[]{firstPosition, lastPosition};
}
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) {
// 下一轮搜索区间是 [mid + 1..right]
left = mid + 1;
} else {
// nums[mid] > target，下一轮搜索区间是 [left..mid]
right = mid;
}
}
// 退出循环以后不能确定 nums[left] 是否等于 target，因此需要再判断一次
if (nums[left] == target) {
return left;
}
return -1;
}
private int findLastPosition(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (nums[mid] > target) {
// 下一轮搜索区间是 [left..mid - 1]
right = mid - 1;
} else
// 下一轮搜索区间是 [mid..right]
left = mid;
}
}
// 主程序先执行 findFirstPosition，能执行到 findLastPosition 说明数组中一定存在等于 target 的元素，因此这里不用判断 nums[left] 是否等于 target
return left;
}
}
# 对参考代码的说明
findFirstPosition()，分成三种情况。
温馨提示：下面的描述有一点啰嗦，只是为了说清楚，读者了解思路就可以了，不必全部看完。
情况 1 ：当 nums[mid] < target 时
mid一定不是target第一次出现的位置；- 由于数组有序，
mid的左边一定比nums[mid]还小，因此mid的左边一定不是target第一次出现的位置； mid的右边比nums[mid]还大，因此mid的右边 有可能 存在target第一次出现的位置。
因此下一轮搜索区间是 [mid + 1..right]，此时设置 left = mid + 1；
情况 2 ：当 nums[mid] == target 时
mid有可能是target第一次出现的位置；mid的左边也有可能是target第一次出现的位置；mid的右边一定不是target第一次出现的位置。
因此下一轮搜索区间在 [left..mid]，此时设置 right = mid。
情况 3 ：当 nums[mid] > target 时
mid一定不是target第一次出现的位置；mid的右边也一定不是target第一次出现的位置；mid的左边有可能是target第一次出现的位置，因此下一轮搜索区间在[left..mid - 1]，此时设置right = mid - 1。
重点：把情况 ② 和情况 ③ 合并，即当
nums[mid] >= target的时候，下一轮搜索区间是[left..mid]，此时设置right = mid。这样做是因为：只有当区间分割是[left..mid]和[mid + 1..right]的时候，while(left < right)退出循环以后才有left == right成立。
这里感谢 @dynamite-z 朋友纠正了一处笔误。
findLastPosition() 也可以类似分析，这里省略。
在本题解中，while(left < right) 只表示退出循环以后有 left == right 成立，不表示搜索区间为左闭右开区间，本题解以及我的其它题解中，对循环不变量的定义均为：在 nums[left..right] 中查找目标元素。
复杂度分析：
- 时间复杂度：
，这里 是数组的长度，两个子问题都是二分查找，因此时间复杂度为对数级别； - 空间复杂度：
，只使用了常数个数的辅助变量。
作者：liweiwei1419 链接：https://suanfa8.com/binary-search/solutions-1/0034-find-first-and-last-position-of-element-in-sorted-array 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。