【深基13.例1】查找

题意

给出一个单调不减数组和若干询问。每次要找目标值第一次出现的编号；不存在时输出 -1。题目使用从 1 开始的编号。

思路

bisect_left(numbers, value) 返回 value 应该插入的最左位置。若该位置仍在数组内，并且元素确实等于 value，它就是第一次出现的位置；否则数组中没有这个值。

例如数组为 1 3 3 3 5，查询 3 时得到下标 1。Python 下标从 0 开始，输出时加一得到题目编号 2。

Python 知识

bisect_left 等价于 C++ 的 lower_bound，返回第一个不小于目标的位置。
map(first_position, queries) 把同一个查询函数应用到每个询问；print(*) 再把答案按空格展开。
/home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：大量整数使用 sys.stdin.buffer.read().split() 一次读取。
/home/rainboy/mycode/hugo-blog/content/program_language/python/map_reduce_filter.md：已有函数时，map 可以简洁表达一一映射。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16import sys
from bisect import bisect_left


data = list(map(int, sys.stdin.buffer.read().split()))
n, m = data[:2]
numbers = data[2:2 + n]
queries = data[2 + n:2 + n + m]


def first_position(value):
    index = bisect_left(numbers, value)
    return index + 1 if index < n and numbers[index] == value else -1


print(*map(first_position, queries))

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69/**
 * Author by Rainboy blog: https://rainboylv.com github: https://rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-08-14 19:07
 */

/* P2249 【深基13.例1】查找 */
/* 在单调不减数组中二分查找目标第一次出现的位置（从 1 开始编号）。 */

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

const int MAXN = 1000005;
const int MAXM = 100005;

int n, m;
int a[MAXN]; // 单调不减数组
int x;       // 当前要查找的目标值

// check 单调：false false ... false true true ... true
// a[pos] >= x 从某处开始恒为 true
bool check(int pos) {
    return a[pos] >= x;
}

// 在 [l, r] 中查找第一个满足 check(pos) 的位置。
// 要求 r 是一个真实或虚拟的可行位置。
int first_true(int l, int r) {
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 哨兵位置 n+1：表示不存在 >= x 的元素。
    a[n + 1] = INT_MAX;

    for (int i = 1; i <= m; i++) {
        cin >> x;

        // 第一个 a[pos] >= x 的位置，若等于 x 说明 x 存在
        int pos = first_true(1, n + 1);
        if (pos <= n && a[pos] == x) {
            cout << pos;
        } else {
            cout << -1;
        }
        if (i == m) {
            cout << '\n';
        } else {
            cout << ' ';
        }
    }

    return 0;
}

STL 写法

把数组放进 vector<ll>，每个询问直接调用 lower_bound，它返回第一个“不小于 x”的位置：下界落在区间末尾、或下界处的值不等于 x 时输出 -1，否则把下标加一得到题目要的编号。相比手写二分，这里不用维护 l、r 和 mid，边界判断只写成一句；lower_bound 与 Python 的 bisect_left 语义完全一致。

对应的 cppbook 章节：二分查找：是否存在与边界位置

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 00:18
 * update_at: 2026-10-07 00:27
 */
/* P2249 【深基13.例1】查找 */
/* STL 写法：用 vector<ll> 保存单调不减数组，用 lower_bound 找第一个不小于 x 的位置。 */

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

typedef long long ll;

ll n, m;
vector<ll> numbers; // 单调不减的待查询数组，numbers[0] 是第 1 个数

void read_input() {
    cin >> n >> m;
    numbers.resize(n);
    for (ll i = 0; i < n; i++) {
        cin >> numbers[i];
    }
}

// 依次回答 m 个询问，答案用空格隔开输出在同一行。
void solve() {
    for (ll i = 1; i <= m; i++) {
        ll x;
        cin >> x;

        // lower_bound 返回第一个“不小于 x”的位置（迭代器）。
        auto it = lower_bound(numbers.begin(), numbers.end(), x);

        if (it == numbers.end() || *it != x) {
            // 下界跑到末尾，或下界处的值并不等于 x，说明 x 不存在。
            cout << -1;
        } else {
            // it - numbers.begin() 是 0 开始的下标，题目要的是 1 开始的编号。
            cout << it - numbers.begin() + 1;
        }

        if (i == m) {
            cout << '\n';
        } else {
            cout << ' ';
        }
    }
}

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

    read_input();
    solve();

    return 0;
}

复杂度

每次查询时间复杂度为 $O(\log n)$ ，总时间复杂度为 $O(m\log n)$ ；保存数组和询问需要 $O(n+m)$ 空间。

总结

bisect_left 只给出插入位置，因此必须再检查该位置是否真的等于目标值，并注意把 Python 的零下标转换成题目的编号。