C++，全部TLE

Nemo_ @ 2023-07-13 07:31:25

using namespace std;
int a[1000010];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) 
    {
        cin>>a[i];
    }
    int r=n,l=1;
    while(m--)
    {
        int c,ans;
        cin>>c;
        int mid;
        while(l<r)
        {
            mid=1+((r-l)>>1);
            if(a[mid]>=c) r=mid-1;
            else l=mid+1;

        }
        if(a[l]==c)
        {
            cout<<l<<" ";
        }
        else
        {
            cout<<-1<<' ';
        }
    }   
    return 0;
}

by 2021CHD @ 2023-07-13 07:36:52

@Nemo_

            while(l<r)
        {
            mid=1+((r-l)>>1);
            if(a[mid]>=c) r=mid-1;
            else l=mid+1;

        }

在a[mid]==c成立时会出现错误（输出-1） （TLE 暂时还没看出来）

by Nemo_ @ 2023-07-13 07:41:08

@2021CHD 谢谢dalao

by Nemo_ @ 2023-07-13 07:44:05

@2021CHD 改了之后

if(a[mid]>c) r=mid;

样例输出变成了-1,2，-1,咋办？

by 2021CHD @ 2023-07-13 07:49:34

@Nemo_ 应该改成

if(a[mid]>=c) r=mid;

另外，要把

mid=1+((r-l)>>1);

改成

mid=(l+r)>>1;

by Nemo_ @ 2023-07-13 07:59:07

@2021CHD 谢谢dalao 但是把

if(a[mid]>=c) r=mid;

改完后输出1，-1，-1 把

mid=(l+r)>>1;

也改了还是1，-1，-1

by Henry2012 @ 2023-07-13 08:07:03

每次循环前l,r没赋初值

by Henry2012 @ 2023-07-13 08:07:18

@Nemo_

by 0x282e202e2029 @ 2023-07-13 08:08:21

用 lower_bound 不行吗（

ans = lower_bound(a + 1, a + n + 1, c) - a; 
if(c == a[ans])
{
    printf("%d ", ans);
}
else
{
    printf("-1 ");
}

by Nemo_ @ 2023-07-13 08:12:49

@Yejiacheng 教练给的二分的模板，要求把模板背过按模板写，不让用函数

by 0x282e202e2029 @ 2023-07-13 08:13:43

6