【深基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;
}

复杂度

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

总结

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

【深基13.例1】查找

目录

题意

思路

Python 知识

代码

复杂度

总结