不明白为什么我这个二分一个测试点都过不了

2021xiaohu @ 2023-03-31 22:32:33

#include<bits/stdc++.h>
using namespace std;
long long a[110000]
long long n,t;
int fum(long long s)
{
    int re=1;
    int lf=n;
    int mip=0;
    while(re<=lf)
    {
        mip=re+(lf-re)/2;
        if(a[mip]==s)
        return mip;
        else if(a[mip]>s)
        lf=mip-1;
        else if(a[mip]<s)
        re=mip+1;
    }
    return 0;
}
int main()
{
    cin>>n>>t;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=t;i++)
    {
        long long b;
        cin>>b;
        if(fum(b,n)!=0)
        {
            int k=fum(b,n);
            while(a[k-1]==a[k])
            k--;
          cout<<k<<" ";

        }
        else
        cout<<-1<<" "; 
    }
    return 0;
}

by Ruiqun2009 @ 2023-03-31 22:49:31

@2021xiaohu 有三点问题：

1. 没关流同步
2. 搜了两次
3. 所有数如果全部是相同的（要查找的数）可以卡掉

by 2021xiaohu @ 2023-04-01 19:13:05

@Ruiqun2009 我知道后面两点了，第一点没关流同步是什么，大佬

by 2021xiaohu @ 2023-04-01 19:26:18

@Ruiqun2009 大佬可是这个连一个测试点都过不了

#include<bits/stdc++.h>
using namespace std;
int a[110000];
int n,t;
int fum(int s)
{
    int re=1;
    int lf=n;
    int mip=0;
    while(re<=lf)
    {
        mip=re+(lf-re)/2;
        if(a[mip]==s)
        return mip;
        else if(a[mip]>s)
        lf=mip-1;
        else if(a[mip]<s)
        re=mip+1;
    }
    return 0;
}
int main()
{
    cin>>n>>t;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=t;i++)
    {
        int b;
        cin>>b;
         int k=fum(b);
        if(k!=0)
        {
            while(a[k-1]==a[k])
            k--;
          cout<<k<<" ";

        }
        else
        cout<<-1<<" "; 
    }
    return 0;
}

by 2021xiaohu @ 2023-04-01 20:52:30

@Ruiqun2009 改好了麻烦看一下大佬

#include<bits/stdc++.h>
using namespace std;
int a[110000];
int n,t;
int fum(int s)
{
    int re=1;
    int lf=n;
    int mip=0;
    while(re<=lf)
    {
        mip=re+(lf-re)/2;
        if(a[mip]==s&&a[mip-1]!=a[mip])
        return mip;
        else if(a[mip]>=s)
        lf=mip-1;
        else if(a[mip]<s)
        re=mip+1;
    }
    return 0;
}
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>t;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=t;i++)
    {
        int b;
        cin>>b;
         int k=fum(b);
        if(k!=0)
        {
          cout<<k<<" ";

        }
        else
        cout<<-1<<" "; 
    }
    return 0;
}