C++二分查找实战：在有序数组中寻找最接近目标值的数字

我来帮你实现这个“找到最接近目标值的数字”的 C++ 解决方案。 ## 🎯 问题分析 这个问题要求在一个**已排序**的数组中，找到最接近目标值 `k` 的数字。关键点： 1. 数组已排序 → 可以使用二分查找优化 2. “最接近”意味着绝对值差最小 3. 如果有多个数字距离相同 → 返回最小的那个 ## 📝 C++ 实现方案 ### 方案一：二分查找法（推荐） ```cpp #include <iostream> #include <vector> #include <cmath> using namespace std; int findClosestNumber(const vector<int>& arr, int k) { int left = 0; int right = arr.size() - 1; // 处理边界情况 if (k <= arr[0]) return arr[0]; if (k >= arr[right]) return arr[right]; // 二分查找 while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == k) { return arr[mid]; } else if (arr[mid] < k) { left = mid + 1; } else { right = mid - 1; } } // 此时 left > right，检查 left 和 right 位置的元素 // left 指向第一个大于 k 的元素，right 指向最后一个小于 k 的元素 int candidate1 = arr[right]; // 小于 k 的最大的数 int candidate2 = arr[left]; // 大于 k 的最小的数 int diff1 = abs(candidate1 - k); int diff2 = abs(candidate2 - k); // 比较距离，距离相同返回较小的 if (diff1 < diff2) { return candidate1; } else if (diff2 < diff1) { return candidate2; } else { return min(candidate1, candidate2); } } int main() { int n; cin >> n; vector<int> arr(n); for (int i = 0; i < n; i++) { cin >> arr[i]; } int k; cin >> k; int result = findClosestNumber(arr, k); cout << result << endl; return 0; } ``` ### 方案二：简化版二分查找 ```cpp #include <iostream> #include <vector> #include <cmath> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<int> arr(n); for (int i = 0; i < n; i++) { cin >> arr[i]; } int k; cin >> k; // 使用 lower_bound 找到第一个 >= k 的位置 auto it = lower_bound(arr.begin(), arr.end(), k); int result; if (it == arr.begin()) { result = arr[0]; } else if (it == arr.end()) { result = arr[n - 1]; } else { int candidate1 = *it; // 第一个 >= k 的数 int candidate2 = *(it - 1); // 最后一个 < k 的数 int diff1 = abs(candidate1 - k); int diff2 = abs(candidate2 - k); if (diff1 < diff2) { result = candidate1; } else if (diff2 < diff1) { result = candidate2; } else { result = min(candidate1, candidate2); } } cout << result << endl; return 0; } ``` ## 🔍 算法详解 ### 核心思路 1. **二分查找定位**：找到目标值 `k` 应该插入的位置 2. **候选元素比较**：比较该位置前后的两个元素（一个小于等于 k，一个大于等于 k） 3. **距离计算**：计算两个候选元素与 k 的绝对距离 4. **处理平局**：距离相同时返回较小的数字 ### 时间复杂度分析 - **二分查找**：O(log n) - **整体复杂度**：O(log n) - 相比线性扫描 O(n) 更高效 ## ⚠️ 边界情况处理 | 情况 | 处理方式 | |------|----------| | k 小于所有元素 | 返回第一个元素 | | k 大于所有元素 | 返回最后一个元素 | | k 在数组中 | 直接返回该元素 | | 距离相等 | 返回较小的数字 | ## 🚀 性能优化建议 1. **使用 `lower_bound`**：C++ STL 的 `lower_bound` 已经优化得很好 2. **避免重复计算**：缓存距离计算结果 3. **提前返回**：找到 exact match 时立即返回 ## 🎨 扩展功能 ### 1. 返回所有最接近的数字 ```cpp vector<int> findAllClosest(const vector<int>& arr, int k) { int closest = findClosestNumber(arr, k); vector<int> result; for (int num : arr) { if (abs(num - k) == abs(closest - k)) { result.push_back(num); } } return result; } ``` ### 2. 处理浮点数数组 ```cpp double findClosestDouble(const vector<double>& arr, double k) { auto it = lower_bound(arr.begin(), arr.end(), k); if (it == arr.begin()) return arr[0]; if (it == arr.end()) return arr.back(); double candidate1 = *it; double candidate2 = *(it - 1); double diff1 = fabs(candidate1 - k); double diff2 = fabs(candidate2 - k); if (diff1 < diff2) return candidate1; if (diff2 < diff1) return candidate2; return min(candidate1, candidate2); } ``` ## 📚 学习资源推荐 1. **C++ 二分查找相关**： - `std::lower_bound` 官方文档 - `std::upper_bound` 官方文档 - `std::binary_search` 官方文档 2. **算法学习**： - 《算法导论》中的二分查找章节 - LeetCode 相关题目： - 704. 二分查找 - 35. 搜索插入位置 - 658. 找到 K 个最接近的元素 ## 💡 开发建议 1. **测试用例设计**： ```cpp // 测试用例 vector<int> test1 = {1, 3, 5, 7, 9}; // k=4 → 应该返回3或5？根据题意返回3（距离相同取小的） // k=6 → 返回5（距离1）或7（距离1）→ 返回5 ``` 2. **代码健壮性**： - 检查输入数组是否为空 - 验证数组是否已排序 - 处理大数溢出情况 3. **调试技巧**： - 打印中间变量查看二分查找过程 - 使用断言验证边界条件 ######[AI写代码神器 | 1612点数解答 | 2026-03-15 18:48:06]