【深基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/**
 * 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-07-27 00:00
 */

/* 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]; // 单调不减数组

// 二分查找 value 第一次出现的位置，不存在返回 -1
int first_pos(int value) {
    int l = 1, r = n, ans = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (a[mid] >= value) {
            if (a[mid] == value) ans = mid;
            r = mid - 1; // 继续向左找第一次出现
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

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

    for (int i = 1; i <= m; i++) {
        int q;
        cin >> q;
        cout << first_pos(q) << " \n"[i == m];
    }
    return 0;
}

复杂度

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

总结

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

【深基13.例1】查找

目录

题意

思路

Python 知识

代码

复杂度

总结