20分，为啥不能用lower_bound？

shuhao @ 2024-01-24 11:51:47

#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1e6+5;
int n, m;
int a[N];
int q;

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for(int i = 1; i <= m; i++)
    {
        scanf("%d", &q);
        int ans = lower_bound(a+1, a+n+1, q) - a;
        if(a[ans] > q) ans = -1;
        printf("%d ", ans);
    }

    return 0;
}

by JustPureH2O @ 2024-01-24 12:02:12

不是不能用，是你的无解判断必须打成a[ans] != q。如果数据出现一个比输入中最大的数还大的数，迭代器会返回数组尾端，此时它的后面没有元素，自然a[ans] > q也就不一定成立，就会出现判断错误

#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1e6+5;
int n, m;
int a[N];
int q;

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for(int i = 1; i <= m; i++)
    {
        scanf("%d", &q);
        int ans = lower_bound(a+1, a+n+1, q) - a;
        if(a[ans] != q) ans = -1; // 此处大于号改为不等号！！！
        printf("%d ", ans);
    }

    return 0;
}

而且速度和常规二分差不多