P2249 【深基13.例1】查找

记录112

#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int a[N]; int n,m,q; int f_first(int x){//找到第一个下标(二分查找修改版) int l=1,r=n;//左右边界 int pos=-1;//返回下标位置 while(l<=r){//满足查找 int mid=(l+r)/2;//中间值 if(a[mid]==x){//找到了 pos=mid;//记录下标 r=mid-1;//缩小右边界(找第一个下标) }else if(a[mid]>x) r=mid-1;//缩小有边界 else l=mid+1;//缩小左边界 } return pos;//返回下标 } int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=m;i++){ cin>>q; cout<<f_first(q)<<" "; } return 0;//结束程序 }

前言

我是一名专注信奥赛（CSP-J/S、NOIP）的教练。

• 如果你觉得这篇题解对你有帮助，欢迎点击关注我的CSDN账号，我会持续更新高质量算法解析。
• 我深知算法思维的构建远比单纯通过题目更重要，本系列题解不局限于AC代码的堆砌，而是致力于拆解题目背后的逻辑链条与核心知识点
• 备赛路上若遇瓶颈，欢迎随时评论或私信，我将甄选典型疑难问题，通过视频讲解或撰写专项文章的形式，为你提供深度答疑。

题目传送门https://www.luogu.com.cn/problem/P2249

突破口

输入 n 个不超过 10的9次方 的单调不减的（就是后面的数字不小于前面的数字）非负整数 a1​,a2​,…,an​，然后进行 m 次询问。对于每次询问，给出一个整数 q，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 −1 。

🔍 一、题目本质与核心要求

🎯 问题重述

• 给定一个长度为 n 的非负整数序列a[1..n]
• 序列满足：单调不减（即a[i] ≤ a[i+1]）
• 进行m次查询，每次给一个整数q
• 要求：输出q在序列中第一次出现的下标（从 1 开始）
• 若未出现，输出-1

✅ 关键词提炼：

• 有序数组→ 可用二分查找
• 第一次出现→ 需要“左边界”二分
• 多次查询→ 每次 O(log n) 比 O(n) 快得多
• 数据量大（n ≤ 1e6, m ≤ 1e5）→ 必须用高效算法

📌 样例解析（输入 #1）

n=11, m=3 a = [1, 3, 3, 3, 5, 7, 9, 11, 13, 15, 15] queries: q = 1, 3, 6

• q=1：首次出现在位置1
• q=3：首次出现在位置2（不是 3 或 4！）
• q=6：不存在 →-1

输出：1 2 -1

🧠 二、核心知识点拆解

1.为什么能用二分？

• 因为数组单调不减（sorted non-decreasing）
• 二分查找的前提是有序性

2.普通二分 vs “找第一个出现位置”

• 普通二分：找到任意一个等于x的位置即可
• 本题要求：最左边的等于x的位置
• 解法：在找到a[mid] == x后，不立即返回，而是继续向左搜索

💡 这称为“lower_bound”（下界）问题

3.时间复杂度分析

• 每次查询：O(log n)
• 总时间：O(m log n) ≈ 1e5 × log₂(1e6) ≈ 1e5 × 20 =2e6 操作✅ 可接受
• 若暴力扫描：O(m × n) ≈ 1e11 ❌ 超时

4.边界处理

• 数组下标从1 开始（题目要求输出从 1 编号）
• 二分初始：l = 1,r = n
• 未找到时返回-1

代码分析

#include<bits/stdc++.h> using namespace std; const int N = 1e6 + 10; int a[N]; // 存储序列，下标从1开始 int n, m, q;

• N = 1e6 + 10：略大于最大 n（1e6），防越界
• 全局变量自动初始化为 0

int f_first(int x) { // 找 x 第一次出现的位置（1-based） int l = 1, r = n; // 搜索区间 [1, n] int pos = -1; // 默认未找到

while (l <= r) { int mid = (l + r) / 2; // 中点（注意：此处无溢出风险，因 n ≤ 1e6）

• 标准二分循环条件：l <= r

if (a[mid] == x) { pos = mid; // 记录当前位置 r = mid - 1; // 继续向左找更早的出现位置！ }

🔥这是本题最关键的逻辑！

• 即使找到了x，也不能停
• 必须尝试在[l, mid-1]中找更靠左的x

else if (a[mid] > x) r = mid - 1; // x 在左半部分 else l = mid + 1; // a[mid] < x，x 在右半部分 } return pos; // 若从未找到，pos 保持 -1 }

int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; // 读入序列，1-based

for (int i = 1; i <= m; i++) { cin >> q; cout << f_first(q) << " "; } return 0; }

潜在优化与注意事项

✅ 建议优化 IO（虽原代码没写，但实际竞赛应加上）：

ios::sync_with_stdio(false); cin.tie(nullptr);

与其他方法对比