二分模板，为什么过不了，求大佬解答

Ginaaaa @ 2023-03-25 10:48:23

#include<stdio.h>
int n,m;
int x;
int a[100005];
int check(int target){
    int left=0;
    int right=n-1;

    while(left<=right){
        int mid=left+right>>1;
        if(a[mid]>target) right=mid-1;
        else if(a[mid]<target) left=mid+1;
        else return mid;
    }
    return -1;
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) 
      scanf("%d",&a[i]);
    while(m--){
    scanf("%d",&x);
    int res = check(x);
    printf("%d ",res);
    }
    return 0;
}

by metaphysis @ 2023-03-25 11:00:20

@Ginaaaa

此题给定的数据由于是单调不减的，可能存在值相同的数据，这样您的实现就无法保证满足题目的需要，您的实现只能保证值互不相同的情形下结果的正确，例如以下数据：

10 1
1 1 1 1 1 1 1 1 1 1
1

您的实现无法得到正确输出。

by metaphysis @ 2023-03-25 11:01:18

需要考虑值相同的情形下如何保证结果的正确。

by metaphysis @ 2023-03-25 11:02:30

可以自己实现或者考虑使用STL中的lower_bound。

by Ginaaaa @ 2023-03-25 12:48:07

#include<bits/stdc++.h>
using namespace std;
int n,m;
int x;
int a[100005];
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) 
      scanf("%d",&a[i]);
    sort(a,a+n);
    while(m--){
    scanf("%d",&x);
    int res = lower_bound(a,a+n,x)-a;
    if(x!=a[res]) printf("-1 ");//没有，输出-1
        else printf("%d ",res);//有，输出ans
    }
    return 0;
}

@metaphysis

by Ginaaaa @ 2023-03-25 12:48:32

@Ginaaaa 还是不能ac

by metaphysis @ 2023-03-25 13:51:49

@Ginaaaa

#include<bits/stdc++.h>
using namespace std;
int n,m;
int x;
//int a[100005];
int a[1000005];
int main(){
    scanf("%d %d",&n,&m);
    //for(int i=1;i<=n;i++)
    for (int i = 0; i < n; i++)
      scanf("%d",&a[i]);
    //sort(a,a+n);
    while(m--){
    scanf("%d",&x);
    int res = lower_bound(a,a+n,x)-a;
    if(res >= n || x!=a[res]) printf("-1 ");//没有，输出-1
        else printf("%d ", res + 1);//有，输出ans
    }
    return 0;
}

by _Cyan_ @ 2023-03-25 14:22:02

#include<bits/stdc++.h>
using namespace std;
int n,m;
int x;
vector<int> a;
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        a.push_back(x);
    } 

    while(m--){
        scanf("%d",&x);
        int it=lower_bound(a.begin(),a.end(),x)-a.begin()+1;
        if(a[it-1]==x)cout<<it<<' ';
        else printf("-1 ");
    }
    return 0;
}

by _Cyan_ @ 2023-03-25 14:23:41

@Ginaaaa 你再看一看