P2249 【深基13.例1】查找（洛谷题面）

题目

题目描述：

输入 nn 个不超过 10910^9 的单调不减的（就是后面的数字不小于前面的数字）非负整数 a1,a2,…,ana_1,a_2,\dots,a_{n}，然后进行 mm 次询问。对于每次询问，给出一个整数 qq，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 −1-1 。

输入格式：

第一行 22 个整数 nn 和 mm，表示数字个数和询问次数。

第二行 nn 个整数，表示这些待查询的数字。

第三行 mm 个整数，表示询问这些数字的编号，从 11 开始编号。

输出格式：

输出一行，mm 个整数，以空格隔开，表示答案。

数据范围与说明：

数据保证，1≤n≤1061 \leq n \leq 10^6，0≤ai,q≤1090 \leq a_i,q \leq 10^9，1≤m≤1051 \leq m \leq 10^5

本题输入输出量较大，请使用较快的 IO 方式。

输入输出样例 #1

输入：

1
2
3
11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6

输出：

1
1 2 -1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    while (m--) {
        int x;
        scanf("%d", &x);
        auto it = lower_bound(arr.begin(), arr.end(), x);
        int idx = it - arr.begin();
        if (it == arr.end() || *it != x) {
            printf("-1 ");
        } else {
            printf("%d ", idx+1);
        }
    }
    return 0;
}