【题目来源】
洛谷：P2249 【深基13.例1】查找 - 洛谷
【题目描述】
输入 \(n\) 个不超过 \(10^9\) 的单调不减的（就是后面的数字不小于前面的数字）非负整数 \(a_1,a_2,\dots,a_n\)，然后进行 \(m\) 次询问。对于每次询问，给出一个整数 \(q\)，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 \(−1\)。
【输入】
第一行 \(2\) 个整数 \(n\) 和 \(m\)，表示数字个数和询问次数。
第二行 \(n\) 个整数，表示这些待查询的数字。
第三行 \(m\) 个整数，表示询问这些数字的编号，从 \(1\) 开始编号。
【输出】
输出一行，\(m\) 个整数，以空格隔开，表示答案。
【输入样例】
11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6
【输出样例】
1 2 -1
【解题思路】
【算法标签】
《洛谷 P2249 查找》 #二分#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 全局变量：
// n: 数组长度
// m: 查询次数
// q: 当前查询值
// tmp: 临时变量（未使用）
// a[1000005]: 存储有序数组
int n, m, q, tmp;
int a[1000005];/*** 二分查找函数* @param q 要查找的值* @return 值在数组中的位置（从1开始），未找到返回-1*/
int find(int q)
{int l = 1, r = n; // 初始化左右边界while (l < r){int mid = l + (r - l) / 2; // 计算中间位置，防止溢出// 调整搜索范围if (a[mid] >= q){r = mid; // 搜索左半部分}else{l = mid + 1; // 搜索右半部分}}// 检查是否找到目标值if (a[l] == q){return l;}else{return -1;}
}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 << find(q) << " "; // 输出查找结果}return 0;
}
// 使用lower_bound再做一遍
#include <bits/stdc++.h>
using namespace std;// 全局变量：
// n: 数组长度
// m: 查询次数
// q: 当前查询值
// mark: 存储查找结果的位置
// a[1000005]: 存储有序数组
int n, m, q, mark;
int a[1000005];int main()
{// 输入数组长度和查询次数cin >> n >> m;// 输入有序数组（从索引1开始存储）for (int i = 1; i <= n; i++){cin >> a[i];}// 处理每个查询for (int i = 1; i <= m; i++){cin >> q; // 输入查询值// 使用lower_bound查找第一个不小于q的元素位置mark = lower_bound(a + 1, a + n + 1, q) - a;// 检查是否找到确切值if (a[mark] == q){cout << mark << " "; // 输出找到的位置}else{cout << "-1 "; // 未找到输出-1}}return 0;
}
【运行结果】
11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6
1 2 -1