AcWing 789. 数的范围

⬅ 返回

1.原题

https://www.acwing.com/problem/content/791/

2.代码

二分模板

#include <iostream>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    int a[n];
    for(int i=0;i<n;i++)cin>>a[i];
    while(m--)
    {
        int l=0,r=n-1;
        int q;
        cin>>q;
        while(l<r)//找左边界
        {
            int mid=(l+r)/2;
            if(a[mid]>=q)r=mid;
            else l=mid+1;
        }
        if(a[l]!=q)cout<<-1<<" "<<-1<<endl;
        else//找右边界
        {
            cout<<l<<" ";
            int l=0,r=n-1;
            while(l<r)
            {
                int mid=(l+r+1)/2;//当条件为l收缩时 这里需要+1
                if(a[mid]<=q)l=mid;
                else r=mid-1;
            }
            cout<<l<<endl;
        }
    }   
    return 0;
}