C++二分查找算法实现及图书馆书籍查找应用

## 🔍 二分查找程序实现思路 二分查找（Binary Search）是一种在**有序数组**中快速查找目标值的算法，时间复杂度为 **O(log n)**，非常适合本题的场景。 ### 📦 核心算法步骤 1. 初始化左指针 `left = 0`，右指针 `right = n - 1`。 2. 当 `left <= right` 时循环： - 计算中间位置 `mid = left + (right - left) / 2`（避免溢出）。 - 比较 `arr[mid]` 与目标值 `target`： - 若相等 → 找到目标，返回 `mid + 1`（因为题目要求输出“第几本书”，从1开始计数）。 - 若 `arr[mid] < target` → 目标在右侧，更新 `left = mid + 1`。 - 若 `arr[mid] > target` → 目标在左侧，更新 `right = mid - 1`。 3. 若循环结束未找到，返回 `n + 1`。 ### ⚙️ C++ 代码实现 ```cpp #include <iostream> #include <vector> using namespace std; int binarySearch(const vector<int>& books, int target) { int left = 0; int right = books.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (books[mid] == target) { return mid + 1; // 找到，返回位置（从1开始） } else if (books[mid] < target) { left = mid + 1; // 目标在右侧 } else { right = mid - 1; // 目标在左侧 } } return books.size() + 1; // 未找到，返回n+1 } int main() { int n, m; cin >> n >> m; vector<int> books(n); for (int i = 0; i < n; i++) { cin >> books[i]; } for (int i = 0; i < m; i++) { int target; cin >> target; cout << binarySearch(books, target) << endl; } return 0; } ``` ### 🛡️ 关键注意事项 1. **输入保证有序**：题目明确说明书籍编号按从小到大排列，这是二分查找的前提条件。 2. **边界处理**： - 使用 `while (left <= right)` 确保所有元素都被检查。 - 计算 `mid` 时使用 `left + (right - left) / 2` 而非 `(left + right) / 2`，防止整数溢出。 3. **输出要求**： - 找到时输出位置从 **1** 开始计数（`mid + 1`）。 - 未找到时输出 **n+1**，符合题目要求。 ### 🚀 性能优化建议 - **使用迭代而非递归**：避免递归调用的栈开销。 - **提前检查边界**：如果目标值小于第一个元素或大于最后一个元素，可直接返回 `n+1`。 - **使用引用传参**：`binarySearch` 函数使用 `const vector<int>&` 避免拷贝。 ### ⚠️ 常见陷阱 1. **死循环**：确保每次迭代都更新 `left` 或 `right`。 2. **索引错误**：注意数组索引从0开始，但输出要求从1开始。 3. **重复元素**：如果存在重复编号，此算法返回第一个找到的位置（不一定是第一个出现的位置）。 ### 📚 扩展学习 - **STL 实现**：C++ 标准库提供了 `std::binary_search`、`std::lower_bound` 等函数。 - **变体问题**：查找第一个/最后一个等于目标值的位置、查找插入位置等。 - **相关算法**：插值查找、指数查找等改进版本。 ######[AI写代码神器 | 893点数解答 | 2026-03-15 18:44:40]