蒟蒻求改，用了二分，但是 TLE

Anoif @ 2024-07-07 21:37:51

#include<bits/stdc++.h>
using namespace std;
int a[1145140];
int bs(int l,int r,int x){
    while(l<r){
        int mid=(l+r)/2;
        if(a[mid]==x) return mid;
        if(a[mid]<x) l=mid;
        else r=mid;
    }
    return -1;
}
int main(){
    int n,m,s; cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++){
        cin>>s;
        cout<<bs(1,n,s)<<" ";
    }
    return 0;
}

by Felixy_2012 @ 2024-07-07 21:45:08

lower_bound不香吗

by dengchengyu @ 2024-07-07 21:48:29

建议改成：

int bs(int l,int r,int x){
    int ans=-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid]==x)ans=mid,r=mid-1;
        else if(a[mid]<x)l=mid+1;
        else r=mid-1;
    }
    return ans;
}

by ZTHu @ 2024-07-07 21:53:49

二分过程中的mid不一定是序列中要查找的数字最先出现的地方

by Crushxl @ 2024-07-07 21:54:08

#include<bits/stdc++.h>
using namespace std;
int a[1145140];
int bs(int l,int r,int x){
    int ans = -1;
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid]==x){
            ans = mid;
            r = mid-1;
        }else if(a[mid]<x){
            l = mid+1;
        }else{
            r = mid-1;
            if(a[mid] == x){
            }
        }
    }
    return ans;
}
int main(){
    int n,m,s; cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++){
        cin>>s;
        cout<<bs(1,n,s)<<" ";
    }
    return 0;
}

首先有一个逻辑错误，a[mid]==x不可以直接return，要继续尽可能向左搜索，因为要找的是第一个出现的元素。

其次是等号，+1-1的边界条件有点问题，估计是T的原因

by BlackWuKong @ 2024-07-10 09:53:50

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+9;
int n,m,a[N];
void work(){
    int ans,l=1,r=n,x;
    cin>>x;
    while (l<=r){
        int mid=l+r>>1;
        if (a[mid]>=x) r=mid-1,ans=mid; 
        else l=mid+1;
    }
    if (a[ans]!=x) cout<<-1<<' ';
    else cout<<ans<<' ';
} 
int main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>a[i];
    while (m--){
        work();
    }
    return 0;
}

by Anoif @ 2024-07-10 20:36:46

谢谢各位大佬！抱歉现在才看到qwq