题目描述

$upper\_bound(a.begin(), a.end(), t)$：返回容器 $a$ (升序) 中第一个大于 $t$ 的迭代器 (你可以理解成位置)，如果 $t$ 在数组范围内，显然返回的位置减一，即 $pos - 1$ 为最后一个小于等于 $t$ 的位置，但是要小心边界。

初学者把迭代器当成指针就行, 慎用解引用操作，即 $*upper\_bound(a.begin(), a.end(), t)$，避免下标越界，最好加个判断。

注意： 本质上是二分法实现（数组需要具有单调性），所以需要排序后使用。

注意： 包含 #include <algorithm>

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for(int i = 0; i < n; ++ i) cin >> a[i];
    sort(a.begin(), a.end());
    while(m --)
    {
        int t;
        cin >> t;
        vector<int>::iterator it = upper_bound(a.begin(), a.end(), t);
		if(it != a.end()) cout << it - a.begin() + 1 << endl;
		else cout << -1 << endl;
    }
    return 0;
}

考虑到 $java$ 同学没有这个函数，我们直接手撕二分(具体到算法阶段再细讲)。

请不要改动我的代码（$l = 0, r = n - 1$）是可以的。

#include<iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
int n, q;
int main()
{
    cin >> n >> q;
    for(int i = 1;i <= n; ++ i) scanf("%d", &a[i]);
    sort(a + 1, a + 1 + n);
    while(q --)
    {
        int k;
        cin >> k;
        int l = 1, r = n;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(a[mid] <= k) l = mid;//找到最后一个 <= k 的位置
            else r = mid - 1;
        }
        if(l == 1 && a[l] > k) cout << 1 << '\n';//特判第一个就大于 k。
        else if(l < n) cout << l + 1 << '\n';
        else cout << -1 << '\n';

    }
    return 0;
}

输入格式

第 $1$ 行，为两个整数 $n, m$。

第 $2$ 行，共 $n$ 个整数 $a[i]$。

接下来 $m$ 行每行一个整数 $t$ 。

输出格式

共 $m$ 行，输出 $a$ 中第一个大于 $t$ 的元素位置 （下标从 $1$ 开始）若不存在则输出 $-1$。

数据范围

$1 ≤ n ≤ 10^5.$

$1 ≤ m ≤ 10^4.$

$1 ≤ a[i] ≤ 10^5.$

输入样例：

3 2
3 2 1
1
4

输出样例：

2
-1