P2249 【深基13.例1】查找

题目描述

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

输入格式

第一行 \(2\) 个整数 \(n\) 和 \(m\)，表示数字个数和询问次数。

第二行 \(n\) 个整数，表示这些待查询的数字。

第三行 \(m\) 个整数，表示询问这些数字的编号，从 \(1\) 开始编号。

输出格式

输出一行，\(m\) 个整数，以空格隔开，表示答案。

输入输出样例 #1

输入 #1

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

输出 #1

1 2 -1 

说明/提示

数据保证，\(1 \leq n \leq 10^6\)，\(0 \leq a_i,q \leq 10^9\)，\(1 \leq m \leq 10^5\)

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

解题思路

数组已排序（单调不减），对每个查询值 q： 用二分查找找到第一个 ≥ q 的位置（lower_bound），

• 若该位置存在且值等于 q → 输出下标
• 否则 → 输出 -1

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

---

C++代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    while (m--) {
        int q;
        cin >> q;

        auto it = lower_bound(a.begin(), a.end(), q);

        if (it != a.end() && *it == q)
            cout << (it - a.begin() + 1) << " ";
        else
            cout << -1 << " ";
    }

    return 0;
}

---

我的做法

#include <iostream>
#include <vector>
using namespace std;

int n;

int binsearch(const vector<int>& a, int target) {
    int left = 0, right = n - 1;
    int ans = n;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (a[mid] >= target) {
            ans = mid;
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }

    return ans;
}

int main() {
    int m;
    cin >> n >> m;

    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    while (m--) {
        int t;
        cin >> t;
        int p = binsearch(a, t);
        if (a[binsearch(a, t)] != t)    cout << -1 << " ";
        else {
            cout << binsearch(a, t) + 1<<" ";
        }
    }

    return 0;
}