题目描述
给你一个按照非递减顺序排列的整数数组 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,则结束。
注意问题:
1. 可能存在找不到值为target的元素,则提前设置答案为[-1,-1],如果找到了则修改左右范围。
2. 可能存在vector为空的情况,此时nLeft=0,nRight=-1,不会进入while循环,则答案[-1,-1]不会更改。
时间复杂度
虽然前面二分是O(logn)的时间复杂度,但后面遍历可能会存在一种最糟糕的情况,即遍历整个数组,时间复杂度为O(n),因此整个算法的时间复杂度应为O(n)。
C++ 代码
class Solution {
public:
vector<int> binarySearch(vector<int>& nums, int target) {
vector<int> res;
int nAns1 = -1, nAns2 = -1; // 找不到或nums为空则直接返回[-1,-1]
int nLeft = 0, nRight = nums.size() - 1;
while (nLeft <= nRight) { // 不用特判nums为空的情况,nums为空,则不会进入while循环
int nMid = nLeft + ((nRight - nLeft) >> 1);
if (nums[nMid] == target) {
nAns1 = nAns2 = nMid;
break;
} else if (nums[nMid] > target) {
nRight = nMid - 1;
} else {
nLeft = nMid + 1;
}
}
// 特殊情况下,很可能遍历整个数组,因此时间复杂度为O(n),上面二分为O(logn),最终时间复杂度为O(n)
if (nAns1 != -1) { // 通过中间点向两边遍历,直到左右端点不为target为止
while (nAns1 > 0 && nums[nAns1 - 1] == target)
--nAns1;
while (nAns2 < nums.size() - 1 && nums[nAns2 + 1] == target)
++nAns2;
}
res.push_back(nAns1);
res.push_back(nAns2);
return res;
}
vector<int> searchRange(vector<int>& nums, int target) {
return binarySearch(nums, target);
}
};
算法2
使用二分查找到任意一个值为target的下标,从该下标位置分别进行左右两个部分的二分查找,即两个二分查找。
同时,该代码采用了原vector进行返回结果,没有申请额外的vector进行存储。
时间复杂度
在进行一个二分查找后(logn),再进行了两次二分查找(2logn==logn),因此整个程序的时间复杂度为O(logn)。
C++ 代码
class Solution {
public:
int searchLeft(vector<int>&nums,int target,int nLeft,int nRight)
{
/*
举例: 5 6 7 8 8 8
如果nums[nMid]>=target,则向左寻找。如果nums[nMid]<target,则向右寻找。
直到nLeft>nRight,则退出循环,返回nLeft即可
*/
while(nLeft<=nRight)
{
int nMid=nLeft+((nRight-nLeft)>>1);
if(nums[nMid]>=target)
{
nRight=nMid-1;
}
else if(nums[nMid]<target)
{
nLeft=nMid+1;
}
}
return nLeft;
}
/*
举例: 8 8 8 9 10 11
如果nums[nMid]<=target,则向右寻找。如果nums[nMid]>target,则向左寻找。
直到nLeft>nRight,则退出循环,返回nRight即可
*/
int searchRight(vector<int>&nums,int target,int nLeft,int nRight)
{
while(nLeft<=nRight)
{
int nMid=nLeft+((nRight-nLeft)>>1);
if(nums[nMid]>target)
{
nRight=nMid-1;
}
else if(nums[nMid]<=target)
{
nLeft=nMid+1;
}
}
return nRight;
}
vector<int> binarySearch(vector<int>& nums, int target) {
int nAns1 = -1, nAns2 = -1; // 找不到或nums为空则直接返回[-1,-1]
int nLeft = 0, nRight = nums.size() - 1;
while (nLeft <= nRight) { // 不用特判nums为空的情况,nums为空,则不会进入while循环
int nMid = nLeft + ((nRight - nLeft) >> 1);
if (nums[nMid] == target) {
nAns1 = nAns2 = nMid;
break;
} else if (nums[nMid] > target) {
nRight = nMid - 1;
} else {
nLeft = nMid + 1;
}
}
if (nAns1 != -1) { // 通过中间点向两边进行二分查找
nAns1=searchLeft(nums,target,0,nAns1);
nAns2=searchRight(nums,target,nAns2,nums.size()-1);
}
nums.clear(); // 直接利用nums数组,不用额外开辟空间
nums.push_back(nAns1);
nums.push_back(nAns2);
return nums;
}
vector<int> searchRange(vector<int>& nums, int target) {
return binarySearch(nums, target);
}
};