第一个点莫名MLE求助，其他点都过了

LxSmill @ 2023-09-11 22:12:45

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,m,t,a[N];
int query(int x,int l,int r)
{ 
    if(l==r&&a[l]!=x) return -1;
    int b=(l+r)/2;
    if(a[b]>x) return query(x,l,b);
    if(a[b]<x) return query(x,b+1,r);
    if(a[b]==x)
    {
        if(a[b-1]!=x) return b;
        else return query(x,l,b);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>t,cout<<query(t,1,n)<<" ";
    cout<<endl;
    return 0;
}

by rnf5114 @ 2023-09-11 22:19:27

递归层数太多了

by LxSmill @ 2023-09-11 22:22:20

@rnfmabj5114 请问有解决办法吗

by rnf5114 @ 2023-09-11 22:28:32

@LxSmill 换成传统二分写法

by zacharyzhong @ 2023-09-11 22:58:28

你说得对，但建议用lower_bound

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000009];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1,x;i<=m;i++)
    {
        cin>>x;
        int p=lower_bound(a+1,a+n+1,x)-a;
        if(a[p]!=x)
            cout<<"-1 ";
        else cout<<p<<' ';
    }
    return 0;
}