求助这道题调了2个小时了但还是WA

_Amy @ 2024-07-06 22:21:05

#include <bits/stdc++.h>
using namespace std;
long long a[1000010];
int n,m;

int lookup(int q){
    int x = 1,y = n + 1;
    while(x <= y){
        int ans = (y + x) / 2;
        if(a[ans] == q) return ans;
        else if(a[ans] > q) y = ans - 1;
        else x = ans + 1; 
    } 
    return -1;
}

int main()
{
    int q;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++) scanf("%lld",&a[i]);
    sort(a + 1, a + n + 1);
    for(int i = 1;i <= m;i ++){
        scanf("%d",&q);
        printf("%d ",lookup(q));
    }
    return 0;
}

by lix_qaq @ 2024-07-07 14:18:26

1.sort没必要，因为原题单调不减

2.可能出现多个相同数据，所以二分找到一个后还要继续判定，不能直接return

#include <bits/stdc++.h>
using namespace std;
long long a[1000010];
int n,m;

int lookup(int q){
    int x = 1,y = n,flag=-1;
    while(x <= y){
        int ans = (y + x) / 2;
        if(a[ans] == q) {
            flag=ans;
            y=ans-1;
        }
        else if(a[ans] > q) y = ans - 1;
        else x = ans + 1; 
    } 
    return flag;
}

int main()
{
    int q;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++) scanf("%lld",&a[i]);
    for(int i = 1;i <= m;i ++){
        scanf("%d",&q);
        printf("%d ",lookup(q));
    }
    return 0;
}

by BlackWuKong @ 2024-07-10 09:55:12

@_Amy

#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;
}