全WA，大佬求帮助

Light_LE @ 2023-09-23 15:16:55

#include<iostream>
using namespace std;
int n,m,a[1000010],b;
int find(int x){
    int l=1,r=n;
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid]==x){
            return mid;
        }
        else if(a[mid]>x){
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    return -1;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    for(int i=0;i<m;++i){
        cin>>b;
        cout<<find(b)<<" ";
    }
    return 0;
}

by WhileTrueRP @ 2023-09-23 15:51:56

#include<iostream>
using namespace std;
int n,m,a[1000010],b;
int find(int x){
    int l=1,r=n,ans = -1;
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid]==x){
            ans = mid;
            r=mid-1;
        }
        else if(a[mid]>x){
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    return ans;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    for(int i=0;i<m;++i){
        cin>>b;
        cout<<find(b)<<" ";
    }
    return 0;
}

by WhileTrueRP @ 2023-09-23 15:52:29

他问的是第一次出现的位置，你这个不能保证是第一次。

by zhouxianzhuo @ 2023-09-23 15:57:03

帮你改了一下

#include<iostream>
using namespace std;
int n,m,a[1000010],b;
int find(int x){
    int l=1,r=n;
    while(l<r){
        int mid=(l+r)/2;
        if(a[mid]>=x){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    return a[r]==x?r:-1;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    for(int i=0;i<m;++i)
    {
        cin>>b;
        cout<<find(b)<<" ";
    }
    return 0;
}

by zhouxianzhuo @ 2023-09-23 16:02:57

这是你原来的代码：

#include<iostream>
using namespace std;
int n,m,a[1000010],b;
int find(int x){
    int l=1,r=n;
    while(l<=r){ //l<r
        int mid=(l+r)/2;
        if(a[mid]==x){ //无法保证是第一个位置
            return mid;
        }
        else if(a[mid]>x){ //应改为>=，否则将找到最后一个
            r=mid-1; //r=mid;
        }
        else{
            l=mid+1;
        }
    }
    return -1;//加上返回r
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    for(int i=0;i<m;++i){
        cin>>b;
        cout<<find(b)<<" ";
    }
    return 0;
}

有用请关注 @zhouxianzhuo