C++怎么实现二分查找？binary_search函数与手写逻辑详解

在C++中处理有序序列的查找需求时，二分查找是最常用也最高效的方法之一。标准库已经提供了现成的binary_search函数，但我们也有必要掌握手写实现，以便在定制比较逻辑或理解底层原理时使用。

使用标准库binary_search函数

C++的<algorithm>头文件中提供了binary_search，它接受两个迭代器和一个目标值，返回bool表示是否找到。默认使用小于运算符比较，也支持自定义比较函数。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> data = {1, 3, 5, 7, 9, 11};
    int target = 7;
    // 使用标准库二分查找
    bool found = std::binary_search(data.begin(), data.end(), target);
    if (found) {
        std::cout << "找到目标值" << std::endl;
    } else {
        std::cout << "未找到目标值" << std::endl;
    }
    return 0;
}

需要注意的是，binary_search只告知是否存在，若想获得位置应使用lower_bound或upper_bound。

手写二分查找逻辑

手写版本核心在于维护左右闭区间，每次取中点比较并收缩范围。以下代码演示了最基本的升序数组查找。

#include <iostream>
#include <vector>

// 返回下标，未找到返回-1
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;
        }
    }
    return -1;
}

int main() {
    std::vector<int> data = {1, 3, 5, 7, 9, 11};
    int idx = binarySearch(data, 5);
    std::cout << "下标: " << idx << std::endl;
    return 0;
}

手写版本的要点

• 循环条件用 left <= right 表示闭区间。
• mid 计算用 left + (right-left)/2 避免整数溢出。
• 每次缩小范围要排除已判断的 mid。

两者对比

常见错误

把无序数组直接用二分查找，或循环写成 left < right 却未正确处理边界，都会导致漏判或死循环。

实际项目中，如果只需要确认存在性且序列标准，直接用binary_search更简洁；若需要下标、处理重复元素或特殊比较，手写逻辑更合适。

C++binary_search二分查找修改时间：2026-07-27 04:06:17