使用二分查找在有序数组中查找小于k的最大元素的实现

以下是完整的代码，通过二分查找来实现在数组中查找小于 `k` 的最大元素： ```cpp #include <iostream> using namespace std; int a[100005], n, k, l, r, mid, ans; int main() { // 读取数组元素个数 cin >> n; // 读取数组元素 for (int i = 1; i <= n; i++) { cin >> a[i]; } // 读取目标值 k cin >> k; // 初始化左边界 l = 1; // 初始化右边界 r = n; // 初始化答案为 n + 1 ans = n + 1; // 二分查找过程 while (l <= r) { // 计算中间位置 mid = (l + r) / 2; // 如果中间元素小于 k if (a[mid] < k) { // 更新答案为中间位置 ans = mid; // 缩小查找范围到右半部分 l = mid + 1; } else { // 缩小查找范围到左半部分 r = mid - 1; } } // 输出小于 k 的最大元素 cout << a[ans] << endl; return 0; } ``` ### 代码解释： 1. **输入处理**：首先读取数组元素的个数 `n`，接着读取 `n` 个元素存储在数组 `a` 中，最后读取目标值 `k`。 2. **二分查找**： - 初始化左边界 `l` 为 1，右边界 `r` 为 `n`，答案 `ans` 初始化为 `n + 1`。 - 在 `l <= r` 的条件下进行二分查找： - 计算中间位置 `mid`。 - 如果 `a[mid] < k`，说明中间元素是小于 `k` 的，更新 `ans` 为 `mid`，并将左边界 `l` 更新为 `mid + 1`，继续在右半部分查找。 - 如果 `a[mid] >= k`，将右边界 `r` 更新为 `mid - 1`，在左半部分查找。 3. **输出结果**：最后输出 `a[ans]`，即小于 `k` 的最大元素。 ######[AI问答 | 598点数解答 | 2026-05-31 13:53:48]