【LeetCode】在排序数组中查找元素的第一个和最后一个位置【三次二分】

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8

输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6

输出: [-1,-1]
来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array

分析：

数组有序，要求时间复杂度是O(log N)，可以联想到二分

先直接在整个数组中二分找target，假设没有找到，那么返回[-1,-1]即可

假设找到了target，位置索引是k，那么在区间[0,k-1],[k+1,n-1]都进行二分寻找target

两个区间寻找target只有四种结果：

假设两个区间找到了target的索引为k1和k3，第一次找到的target索引为k2

1）第一个区间找到，第二个区间没有找到，返回结果:[k1,k2]

2）第一个区间找到，第二个区间找到，返回结果:[k1,k3]

3）第一个区间没有找到，第二个区间找到，返回结果:[k2,k3]

4）第一个区间没有找到，第二个区间没有找到，返回结果:[k2,k2]

总结：先进行一次二分寻找目标值是否存在，然后分别在目标值的两边进行两次二分寻找左右端点

总共三次二分

时间复杂度：O(log N)

空间复杂度:O(1)

class Solution {
public://二分函数
int f(vector<int>& v,int l,int h,int t,int flag)
{
int k1=INT_MAX;
int k3=INT_MIN;
while(l<=h)
{
int mid=(l+h)/2;
if(v[mid]==t)
{
if(flag==1)
k1=min(k1,mid);
else if(flag==3)
k3=max(k3,mid);
else if(flag==2)
return mid;
if(v[l]==t)
{
k1=min(k1,l);
k3=max(k3,l);
}
if(v[h]==t)
{
k1=min(k1,h);
k3=max(k3,h);
}
l++;//找到了也要继续找下去
h--;
}
else if(v[mid]>t)
{
h=mid-1;
}
else if(v[mid]<t)
{
l=mid+1;
}
}
if(flag==1&&k1!=INT_MAX)
return k1;
if(flag==3&&k3!=INT_MIN)
return k3;
return -1;
}
vector<int> searchRange(vector<int>& v, int t)
{
vector<int> ans;
int n=v.size();
int k2=f(v,0,n-1,t,2);//第一次二分判断target是否存在
if(k2==-1)
{
ans.push_back(-1);
ans.push_back(-1);
return ans;
}
//在target的两端各自进行一次二分确定左右区间端点值
int k1=f(v,0,k2-1,t,1);
int k3=f(v,k2+1,n-1,t,3); //根据二分结果确定结果区间
if(k1==-1)
ans.push_back(k2);
else
ans.push_back(k1);
if(k3==-1)
ans.push_back(k2);
else
ans.push_back(k3);
return ans;
}
};