一、题目描述
给你一个按照非递减顺序排列的整数数组 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]
二、题解
思路分析：
题目要求我们找到出现target的第一个位置和最后一个位置，首先，我们想到可以通过暴力枚举的方法来解决该问题，即遍历数组，并记录target第一次出现和最后一次出现的位置。然而，题目要求我们实现时间复杂度为O(log n)的算法，且题目中给出的数组为非递减的数组，因此，我们可以考虑使用二分查找的方法来解决该问题
由于题目中数据量较小，使用遍历的方法也可以通过该题
遍历代码：
class Solution {
public int[] searchRange(int[] nums, int target) {
int first = -1;
int last = -1;
boolean flg = false;//判断是否是第一个位置
for (int i = 0; i < nums.length; i++) {
//第一个位置
if(nums[i] == target && !flg){
first = i;
flg = true;
}
//最后一个位置
//注意处理特殊情况，即最后一个元素在最后一个位置时，nums[i+1]越界
if(nums[i] == target && (i == nums.length - 1 || nums[i+1] != target)){
last = i;
}
}
int[] ret = {first,last};
return ret;
}
}
如何使用二分查找来解决该问题？
题目要求我们找到target在数组中第一次出现和最后一次出现的位置，利用数组非递减的性质
首先我们查找元素的第一个位置：
我们可通过target将数组分为两部分：
其中，左边部分为小于target的元素，右边部分为大于等于target的元素，由于右边区域大于等于target，因此右边区域最左边的值即为target第一次出现的位置，即右边区域的左端点为所求结果
我们定义left指向0位置，right指向最后一个元素，mid指向中间位置
若mid指向的元素落在右边区间，此时nums[mid]大于等于target，需要更新right的值，由于要找的结果（target第一次出现的位置）在此区间内，即mid所指向的位置可能就是最终结果，因此不能将right更新为mid - 1，而应更新为mid
若mid所指向的元素落在左边区间，此时nums[mid]小于target，需要更新 left 的值，由于要找的结果不在此区间内，因此可将left的结果更新为 mid + 1
当left和right之间元素为偶数个时，此时中间元素有两个，应该选择哪一个作为中间元素？
由于我们查找的是右边区间内最左边的元素，因此，应该选择左边的元素作为中间元素
若选择右边元素作为中间元素，能够成功查找到结果吗？
当选择右边元素作为中间元素时，此时会出现死循环的情况，例如：
上图中，当选择右边元素作为中间元素时，mid指向的元素落在右边区间，此时将right更新为mid，再求mid，此时mid仍为指向刚才位置，即落在右边区间，此时再次更新right为mid，再次求mid... 从而死循环
循环条件如何设置？
由于我们将right更新为mid，因此循环的条件应为left < right，若循环条件设置为left <= right，当left = right时，此时找到结果，而结果落在右边区间，此时会更新right的值，而right 更新为mid，即当前位置，从而死循环
分析完以上问题后，我们可以尝试编写查找右边区域最左边元素的代码：
//查找target第一次出现的位置(右边区间的左端点)
int left = 0,right = nums.length - 1,mid = left + (right - left)/2;
//循环条件应设置为left < right
//不能设置为left <= right，否则会死循环
while(left < right){
//当mid所指向的元素落在左边区间时，更新left
if(nums[mid] < target){
left = mid + 1;
}else{//当mid所指向的元素落在右边区间时，此时更新right
//由于右边区间的元素大于等于target，即结果在该区间内，
// 因此不能将right更新为mid - 1,而应更新为mid
right = mid;
}
//更新mid，当有两个中间元素时，mid应指向其中左边的元素
mid = left + (right - left) / 2;
}
此时我们查找target最后一次出现的位置
与查找第一次出现位置的思路相同，我们首先将数组分为两个部分：
其中，左边区间内元素小于等于target，右边区间元素大于target
此时，要找的结果即为左边区间的右端点
同样的，定义left指向0位置，right指向最后一个元素，mid指向中间位置
若mid所指向的元素落在左边区间，此时需要更新left的值，由于要找的结果落在此区间内，即mid所指向的位置可能就是最终结果，因此不能将left更新为mid + 1，而应更新为mid
若mid所指向的元素落在右边区间，此时需要更新right的值，由于要找的结果不在右边区间，因此可将right的值更新为mid - 1
当left和right之间元素为偶数个时，此时中间元素有两个，应该选择哪一个作为中间元素？
由于我们查找的是左边区间内最右边的元素，因此，应该选择右边的元素作为中间元素
即 mid = left + (right - left + 1) / 2;
同样的，当选择左边元素作为中间元素时，也会造成死循环
此时left的值一直更新为当前位置，造成死循环
循环条件的设置：
循环条件也同样应该设置为left < right，否则会死循环
此时我们尝试编写查找左边区间右端点代码：
//查找区间右端点
left = mid;
right = nums.length - 1;
mid = left + (right - left + 1)/2;
while(left < right){
//当mid所指向的值落在右边区域时，更新右端点
if(nums[mid] > target){
right = mid - 1;
}else{//当mid所指向的值落在左边区域时，更新左端点
//由于左边区间的元素小于等于target，即结果在该区间内，
//因此不能将left更新为mid + 1,而应更新为mid
left = mid;
}
//更新mid的值，若有两个中间元素时，mid应指向其中右边的元素
mid = left + (right - left + 1) / 2;
}
完整代码：
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ret = {-1,-1};
//若数组为空，直接返回ret
if(nums.length == 0){
return ret;
}
//查找target第一次出现的位置(右边区间的左端点)
int left = 0,right = nums.length - 1,mid = left + (right - left) / 2;
//循环条件应设置为left < right
//不能设置为left <= right，否则会死循环
while(left < right){
//当mid所指向的元素落在左边区间时，更新left
if(nums[mid] < target){
left = mid + 1;
}else{//当mid所指向的元素落在右边区间时，此时更新right
//由于右边区间的元素大于等于target，即结果在该区间内，
// 因此不能将right更新为mid - 1,而应更新为mid
right = mid;
}
//更新mid，当有两个中间元素时，mid应指向其中左边的元素
mid = left + (right - left) / 2;
}
//此时left = right = mid,使用哪一个变量进行判断和更新都可以
//若数组中无值为target的元素，直接返回ret
if(nums[left] == target){
ret[0] = left;
}else{
return ret;
}
//查找区间右端点
left = mid;
right = nums.length - 1;
mid = left + (right - left + 1)/2;
while(left < right) {
//当mid所指向的值落在右边区域时，更新右端点
if (nums[mid] > target) {
right = mid - 1;
} else {//当mid所指向的值落在左边区域时，更新左端点
//由于左边区间的元素小于等于target，即结果在该区间内，
//因此不能将left更新为mid + 1,而应更新为mid
left = mid;
}
//更新mid的值，若有两个中间元素时，mid应指向其中右边的元素
mid = left + (right - left + 1) / 2;
}
ret[1] = left;
return ret;
}
}
题目来自：
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
参考文章
发表评论