【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;

}

};

【LeetCode】在排序数组中查找元素的第一个和最后一个位置【三次二分】的相关教程结束。