二分查找算法在有序数组中查找特定元素的代码实现

以下是对代码中空缺部分的补充及详细解释。这段代码的主要功能是在一个已排好序的数组里查找特定元素 `k` 的第一个出现位置。若元素 `k` 不存在，就返回 `n + 1`。这里运用了二分查找算法来提升查找效率。 ```cpp #include <iostream> using namespace std; // 定义数组 a 用于存储输入的元素，n 为元素个数，k 为要查找的目标元素 // l 和 r 分别为二分查找的左右边界，mid 为中间位置，ans 用于记录结果 int a[100005], n, k, l, r, mid, ans; int main() { // 输入元素个数 cin >> n; // 循环读取数组元素 for (int i = 1; i <= n; i++) { cin >> a[i]; } // 输入要查找的目标元素 cin >> k; // 初始化左边界为 1 l = 1; // 初始化右边界为 n r = n; // 初始化结果为 n + 1，表示未找到目标元素 ans = n + 1; // 当左边界小于等于右边界时，继续进行二分查找 while (l <= r) { // 计算中间位置 mid = (l + r) / 2; // 当 a[mid] 等于 k 时 if (a[mid] == k) { // 记录当前位置为结果 ans = mid; // 更新右边界，继续向左查找是否有更早出现的 k r = mid - 1; } // 当 a[mid] 小于 k 时 else if (a[mid] < k) { // 更新左边界，向右查找 l = mid + 1; } // 当 a[mid] 大于 k 时 else { // 更新右边界，向左查找 r = mid - 1; } } // 输出结果 cout << ans; return 0; } ``` ### 代码解释： 1. **输入部分**：先输入元素个数 `n`，接着输入 `n` 个元素到数组 `a` 里，最后输入要查找的目标元素 `k`。 2. **初始化部分**：把左边界 `l` 初始化为 1，右边界 `r` 初始化为 `n`，结果 `ans` 初始化为 `n + 1`。 3. **二分查找部分**： - 利用 `while` 循环，当 `l <= r` 时持续查找。 - 算出中间位置 `mid`。 - 若 `a[mid]` 等于 `k`，就记录当前位置 `mid` 为结果 `ans`，并更新右边界 `r = mid - 1`，接着向左查找是否有更早出现的 `k`。 - 若 `a[mid]` 小于 `k`，更新左边界 `l = mid + 1`，向右查找。 - 若 `a[mid]` 大于 `k`，更新右边界 `r = mid - 1`，向左查找。 4. **输出部分**：输出结果 `ans`。 ######[AI问答 | 810点数解答 | 2026-08-09 21:25:34]