C++ 有序数组二分查找小于等于目标的最大值实现详解

好的，这是一个典型的 **二分查找** 应用场景，因为题目中明确说明信号是“逐渐增加的”（即有序的），并且数据规模较大（n <= 100000），因此我们需要用 O(log n) 的算法来快速找到答案。 下面我将为你提供完整的 C++ 程序，并附上详细解释。 ## 🎯 问题分析 - **输入**：已排序（升序）的信号列表，以及一个查询值 k。 - **目标**：找到列表中 **小于等于 k** 的 **最大值**。 - **保证**：一定存在这样的信号。 ## 🚀 解决方案：二分查找（二分查找上界） ### 💡 核心思路 1. 因为信号是 **由小到大** 排序的，我们可以用二分查找来快速定位。 2. 查找的目标是 **最后一个 ≤ k** 的元素（即 upper_bound - 1）。 3. C++ 标准库提供了 `std::upper_bound` 和 `std::lower_bound`，我们可以直接使用，也可以自己手写二分。 ### 📂 代码实现 ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; // 读取信号个数 vector<int> signals(n); for (int i = 0; i < n; i++) { cin >> signals[i]; // 读取所有信号值（已排序） } int k; cin >> k; // 读取查询值 // 使用二分查找：找到第一个 > k 的位置 auto it = upper_bound(signals.begin(), signals.end(), k); // it 指向第一个大于 k 的元素，它前一个元素就是 ≤k 的最大值 int result = *(it - 1); cout << result << endl; return 0; } ``` ### 🔍 代码详解 | 代码部分 | 解释 | |---------|------| | `#include <algorithm>` | 引入二分查找函数库 | | `vector<int> signals(n)` | 定义动态数组存储信号 | | `upper_bound(begin, end, k)` | 返回指向 **第一个 > k** 的元素的迭代器 | | `*(it - 1)` | 因为数组升序，所以前一个元素就是 ≤k 的最大值 | ### ✅ 运行样例 **样例1**： ``` 输入： 5 1 3 4 5 9 3 输出： 3 ``` - `upper_bound(3)` 指向 `4` 所在位置，前一个是 `3` ✅ **样例2**： ``` 输入： 4 1 5 6 9 7 输出： 6 ``` - `upper_bound(7)` 指向 `9` 所在位置，前一个是 `6` ✅ --- ## ⚙️ 进阶与注意事项 ### 🧠 手写二分查找（不依赖 STL） 有时面试或竞赛中不允许使用 `upper_bound`，你可以手写一个： ```cpp int binarySearch(vector<int>& arr, int k) { int left = 0, right = arr.size() - 1; int ans = arr[0]; // 保证至少有一个结果 while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] <= k) { ans = arr[mid]; left = mid + 1; // 继续向右找更大的满足条件的值 } else { right = mid - 1; } } return ans; } ``` ### ⚠️ 常见陷阱 - **边界情况**：如果 k 大于所有信号，应返回最后一个信号（我们的代码 `it - 1` 仍有效）。 - **重复元素**：如果存在多个等于 k 的值，`upper_bound` 会返回第一个大于 k 的位置，前一个仍然是 k 本身，正确。 - **只存在一个信号**：`it - 1` 依然有效，因为 `signals.begin()` 是有效的。 ## 🧰 开发建议 1. **优先使用 STL**：`upper_bound` 和 `lower_bound` 已经过严格优化，比自己手写更稳定、易读。 2. **命名清晰**：变量名如 `signals` 比 `arr` 更贴近业务场景。 3. **输入优化**：如果 n 很大（接近 10^5），建议关闭 C++ 输入输出同步以提升速度： ```cpp ios::sync_with_stdio(false); cin.tie(nullptr); ``` ## 📚 推荐学习资源 - [C++ Reference: std::upper_bound](https://en.cppreference.com/w/cpp/algorithm/upper_bound) - [C++ Reference: std::lower_bound](https://en.cppreference.com/w/cpp/algorithm/lower_bound) - 书籍：《算法竞赛入门经典》—— 刘汝佳 ## 📖 典型应用场景 - **游戏排行榜**：快速找出不超过某个分数的最高排名。 - **嵌入式系统**：查询传感器电压是否在某个阈值区间。 - **数据库索引查找**（B+树类似思想）。 --- ######[AI写代码神器 | 1145点数解答 | 2026-05-29 19:30:20]