C++实现二分查找算法及代码详解

### 🔍 二分查找原理 二分查找（Binary Search）是一种高效的查找算法，它要求被查找的数组必须是有序的。其基本思想是将数组分成两部分，然后比较目标值与中间元素的大小，如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找；如果相等，则找到了目标值。 ### 💻 C++代码实现 ```cpp #include <iostream> #include <vector> // 二分查找函数 int binarySearch(const std::vector<int>& arr, int target) { int left = 0; int right = arr.size() - 1; while (left <= right) { // 计算中间元素的索引 int mid = left + (right - left) / 2; if (arr[mid] == target) { // 找到目标值，返回其索引 return mid; } else if (arr[mid] < target) { // 目标值在右半部分 left = mid + 1; } else { // 目标值在左半部分 right = mid - 1; } } // 未找到目标值，返回 -1 return -1; } int main() { std::vector<int> arr = {1, 3, 5, 7, 9, 11, 13}; int target = 7; int result = binarySearch(arr, target); if (result != -1) { std::cout << "目标值 " << target << " 在数组中的索引是: " << result << std::endl; } else { std::cout << "未找到目标值 " << target << std::endl; } return 0; } ``` ### 📝 代码解释 1. **二分查找函数 `binarySearch`**： - 接收一个有序数组 `arr` 和目标值 `target` 作为参数。 - 使用 `left` 和 `right` 分别表示查找范围的左右边界。 - 在 `while` 循环中，计算中间元素的索引 `mid`。 - 如果中间元素等于目标值，则返回其索引。 - 如果中间元素小于目标值，则将左边界 `left` 更新为 `mid + 1`。 - 如果中间元素大于目标值，则将右边界 `right` 更新为 `mid - 1`。 - 如果循环结束后仍未找到目标值，则返回 -1。 2. **主函数 `main`**： - 定义一个有序数组 `arr` 和目标值 `target`。 - 调用 `binarySearch` 函数进行查找，并将结果存储在 `result` 中。 - 根据查找结果输出相应的信息。 ### ⏱️ 复杂度分析 - **时间复杂度**：$O(log n)$，其中 $n$ 是数组的长度。每次查找都将查找范围缩小一半。 - **空间复杂度**：$O(1)$，只使用了常数级的额外空间。 ######[AI问答 | 731点数解答 | 2026-05-31 13:40:30]