C++ 解决洛谷 P2239 查找问题：思路、数据及代码实现

#### 题目信息 P2239 是洛谷上的一道题目，题目名称为“【深基13.例1】查找”。 ### 📖题目描述 输入 $n$ 个不超过 $10^9$ 的单调不减的（就是后面的数字不小于前面的数字）非负整数 $a_1,a_2,\cdots,a_n$，然后进行 $m$ 次询问。对于每次询问，给出一个整数 $q$，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 $-1$。 ### 📥输入格式 第一行 $2$ 个整数 $n$ 和 $m$，表示数字个数和询问次数。 第二行 $n$ 个整数，表示这些待查询的数字。 第三行 $m$ 个整数，表示询问这些数字的编号，从 $1$ 开始编号。 ### 📤输出格式 $m$ 个整数表示答案。 ### 📋数据范围 $1 \leq n \leq 10^6$，$1 \leq m \leq 10^5$，$1 \leq q \leq 10^9$。 ### 💡样例 #### 输入样例 ```plaintext 11 3 1 3 3 3 5 7 9 11 13 15 15 1 3 6 ``` #### 输出样例 ```plaintext 1 2 -1 ``` ### 🚩代码示例 ```cpp #include <iostream> #include <vector> using namespace std; // 二分查找目标值第一次出现的位置 int binarySearch(vector<int>& arr, int target) { int left = 0, right = arr.size() - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { result = mid; // 继续向左查找第一次出现的位置 right = mid - 1; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } // 因为数组下标从0开始，而题目编号从1开始，所以结果要加1 if (result != -1) result++; return result; } int main() { int n, m; cin >> n >> m; vector<int> arr(n); // 输入数组元素 for (int i = 0; i < n; i++) { cin >> arr[i]; } for (int i = 0; i < m; i++) { int query; cin >> query; // 进行二分查找并输出结果 cout << binarySearch(arr, query); if (i < m - 1) { cout << " "; } } cout << endl; return 0; } ``` 此代码通过二分查找来解决在单调不减序列中查找目标值第一次出现位置的问题，复杂度为 $O(log n)$，可以满足数据范围的要求。 ######[AI问答 | 776点数解答 | 2026-07-28 21:06:57]