掌握C++二分搜索算法（从零开始学会高效查找）

二分搜索的前提条件

• 数组必须是有序的（升序或降序）；
• 支持随机访问（如数组、vector等）；
• 查找目标值必须可比较。

C++实现二分搜索（迭代版本）

下面是一个标准的迭代式二分查找实现，适用于升序排列的数组：

#include <iostream>#include <vector>using namespace std;// 二分查找函数：在有序数组中查找 targetint binarySearch(const 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; // 在左半部分查找        }    }    return -1; // 未找到，返回 -1}int main() {    vector<int> nums = {1, 3, 5, 7, 9, 11, 13, 15};    int target = 7;    int result = binarySearch(nums, target);    if (result != -1) {        cout << "元素 " << target << " 在索引 " << result << " 处找到。" << endl;    } else {        cout << "元素 " << target << " 未找到。" << endl;    }    return 0;}

为什么使用 mid = left + (right - left) / 2？

你可能会看到有些教程写成 mid = (left + right) / 2。虽然结果一样，但当 left 和 right 都很大时，相加可能导致整数溢出。而 left + (right - left) / 2 能有效避免这个问题，是更安全的写法。

递归版本的二分搜索

除了迭代，也可以用递归来实现。虽然递归代码更简洁，但要注意栈空间的消耗：

int binarySearchRecursive(const vector<int>& arr, int left, int right, int target) {    if (left > right) {        return -1;    }    int mid = left + (right - left) / 2;    if (arr[mid] == target) {        return mid;    } else if (arr[mid] < target) {        return binarySearchRecursive(arr, mid + 1, right, target);    } else {        return binarySearchRecursive(arr, left, mid - 1, target);    }}

时间复杂度分析

二分搜索每次将问题规模减半，因此其时间复杂度为 O(log n)，远优于线性查找的 O(n)。这也是为什么高效搜索算法中二分查找如此受欢迎。

常见应用场景

• 在有序数组中查找元素位置；
• 查找第一个/最后一个满足条件的元素（如 LeetCode 中的“搜索插入位置”）；
• 数值计算中的近似解查找（如开平方根）；
• 作为其他高级算法（如归并排序、快速选择）的子过程。

总结

通过本篇C++算法教程，你应该已经掌握了二分搜索的基本原理、两种实现方式以及注意事项。记住：数组必须有序！多加练习，你就能在面试和项目中灵活运用这一高效搜索算法。

小提示：尝试修改代码，使其能查找“第一个大于等于 target 的位置”，这是面试高频题哦！