排好序数组中查找特定元素下标程序的错误修正与优化

### 🐞问题分析 原程序使用二分查找来寻找等于 `k` 的元素的下标，但存在一个问题：当数组中有多个等于 `k` 的元素时，原程序找到任意一个等于 `k` 的元素就会停止查找，而要求是找到第一个等于 `k` 的元素的下标。当循环结束时，若没有在循环内找到等于 `k` 的元素，程序直接输出 `n + 1`，但此时可能 `l` 位置的元素恰好等于 `k`，而原程序没有进行这一步的判断。 ### 💡修改方案 我们可以对二分查找进行修改，当找到等于 `k` 的元素时，不立即停止查找，而是继续向左缩小查找范围，以找到第一个等于 `k` 的元素。在循环结束后，检查 `l` 位置的元素是否等于 `k`。 ### 📝修改后的代码 ```cpp #include <iostream> using namespace std; // 定义数组，数组最大长度为 100005 // 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; if (a[mid] >= k) { // 如果中间元素大于等于 k，更新答案并缩小右边界 if (a[mid] == k) ans = mid; r = mid - 1; } else { // 如果中间元素小于 k，缩小左边界 l = mid + 1; } } // 输出结果 cout << ans; return 0; } ``` ### 🧪代码解释 1. **初始化**：将数组 `a` 的元素输入，读取要查找的数字 `k`，并初始化二分查找的左右边界 `l` 和 `r` 分别为 `1` 和 `n`，初始答案 `ans` 设为 `n + 1`。 2. **二分查找**：在 `l <= r` 的条件下进行二分查找。计算中间位置 `mid`，如果 `a[mid] >= k`，说明目标元素可能在左半部分，更新 `ans` 并将 `r` 更新为 `mid - 1`；如果 `a[mid] < k`，说明目标元素在右半部分，将 `l` 更新为 `mid + 1`。 3. **输出结果**：输出最终答案 `ans`。 ### 📖复杂度分析 - **时间复杂度**：$O(log n)$，因为使用了二分查找。 - **空间复杂度**：$O(n)$，主要用于存储数组。 ######[AI问答 | 819点数解答 | 2026-08-09 21:15:09]