1.问题描述
给你一个按照非递减顺序排列的整数数组 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]
提示
0 <= nums.length <= 105-109 <= nums[i] <= 109nums是一个非递减数组-109 <= target <= 109
难度等级
中等
题目链接
2.解题思路
这道题最后要我们找target的第一个位置和最后一个位置，但是本质上还是找的一个target的题目。因为给我们的是一个非递减的数组，所以我们只要找到了一个target，其他target就在我们找到的target的左边或者右边。
在正式查找之前，我们可以先做一个判断，判断target不存在于数组中的一些特殊情况，比如数组本身就是空的，target小于数组的最小值和target大于数组的最大值，target都不会在数组中。
//如果数组为空数组，直接返回
//检查target是否小于nums的最小值
//检查target是否大于nums的最大值
if(nums.length == 0 || target < nums[0] || target > nums[nums.length - 1]){
return new int[]{-1,-1};
}接着，就是用二分查找，在给定的递增数组中找到一个target的位置，先确定左右指针和二分指针，二分循环的条件是在没有找到target值之前，左右指针不越界，就可以不断循环查找，接着就是更新二分指针，根据二分值与target的大小关系，不断缩小二分范围，直到找到target或者左右指针越界。
//二分查找目标值
int left = 0;
int right = nums.length - 1;
int mid = 0;
while(left <= right){
//更新中间值
mid = (right - left) / 2 + left;
//判断中间值是否等于目标值
if(nums[mid] == target){
break;
}
//中间值小于目标值
if(nums[mid] < target){
left = mid + 1;
}
//中间值大于目标值
if(nums[mid] > target){
right = mid - 1;
}
}我们推出二分循环后，存在两种情况，一种是左右指针越界，说明我们在数组中没有找到target，返回两个-1；另一种情况是我们找到了一个target，这种情况，我们接着往下分析。
//根据查找结果，判断第一个目标值和最后一个目标值的位置
//因为左右指针越界而结束查找
if(left > right){
return new int[]{-1,-1};
}我们既然已经找到了一个target，那么其余的target就在我们找到的这个target左边或者右边，求第一个位置的索引，我们就往左边找，求最后一个位置的索引，我们就往右边找，找的时候，记得不要让指针越界即可。
//找到了目标值
int first = mid;
int last = mid;
//向前寻找第一个位置
while(first >= 0 && nums[first] == target){
first--;
}
//因为找到的是不等于target的位置，要+1恢复到等于target的位置
if(first < nums.length - 1){
first++;
}
//向后寻找最后一个位置
while(last < nums.length && nums[last] == target){
last++;
}
//因为找到的是不等于target的位置，要-1恢复到等于target的位置
if(last > 0){
last--;
}找到第一个位置的索引和最后一个位置的索引之后，将两个索引一起返回就好了。
3.代码展示
class Solution {
public int[] searchRange(int[] nums, int target) {
//如果数组为空数组，直接返回
//检查target是否小于nums的最小值
//检查target是否大于nums的最大值
if(nums.length == 0 || target < nums[0] || target > nums[nums.length - 1]){
return new int[]{-1,-1};
}
//二分查找目标值
int left = 0;
int right = nums.length - 1;
int mid = 0;
while(left <= right){
//更新中间值
mid = (right - left) / 2 + left;
//判断中间值是否等于目标值
if(nums[mid] == target){
break;
}
//中间值小于目标值
if(nums[mid] < target){
left = mid + 1;
}
//中间值大于目标值
if(nums[mid] > target){
right = mid - 1;
}
}
//根据查找结果，判断第一个目标值和最后一个目标值的位置
//因为左右指针越界而结束查找
if(left > right){
return new int[]{-1,-1};
}
//找到了目标值
int first = mid;
int last = mid;
//向前寻找第一个位置
while(first >= 0 && nums[first] == target){
first--;
}
//因为找到的是不等于target的位置，要+1恢复到等于target的位置
if(first < nums.length - 1){
first++;
}
//向后寻找最后一个位置
while(last < nums.length && nums[last] == target){
last++;
}
//因为找到的是不等于target的位置，要-1恢复到等于target的位置
if(last > 0){
last--;
}
return new int[]{first,last};
}
}4.总结
这道题本质上还是一道二分查找题目，只要找到了一个target，其余的target就在我们找到的target前后。好了，这道题没啥难度，就啰嗦到这里，祝大家刷题愉快~