A8022.查找 手写二分解法

由于上升序列，很容易就能想到二分
代码逻辑可以见二分模板
唯一需要注意的是查找的是具体的数，需要判断查找结果是否合法
好了，需要注意的就这些

给出代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN=1000005;
int a[MAXN];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);                    //io加速，相信大家都会，大数据必须开启
    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> a[i];

    while(m--){
        int q;
        cin >> q;
        int l, r, mid;
        l=1; r=n;
        while(l<r){
            mid=(l+r)/2;
            if(a[mid]>=q){
                r=mid;        //如果大于等于，缩小右边界（答案可能合法，r=mid）
            }
            else
                l=mid+1;    //小于，缩小左边界（答案一定不合法，l=mid+1）
        }
        if(a[r]==q)         //判断答案是否合法
            cout << r << " ";    //合法输出(注意是r,mid会WA)
        else
            cout << -1 << " ";    //不合法输出-1
    }
    return 0;
}

时间复杂度：O(n + m log n)
很优秀

欢迎加入团队