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` 函数进行查找。 - 根据返回结果输出相应的信息。 复杂度分析： - 时间复杂度：$O(log n)$，其中 $n$ 是数组的长度。每次查找都将搜索范围缩小一半。 - 空间复杂度：$O(1)$，只使用了常数级的额外空间。 ######[AI问答 | 716点数解答 | 2025-11-13 19:22:49]