C++ 二分查找完全指南：标准库内置函数详解

引言

在C++的日常开发中，二分查找是一个高频使用的算法。虽然我们可以自己手写，但C++标准库已经为我们提供了一套强大而高效的二分查找函数族。它们不仅性能优越（O(log n)），而且经过充分测试，能够正确处理各种边界情况。

本文将详细介绍C++标准库中的二分查找函数，包括它们的用法、区别以及最佳实践。

一、准备工作

所有二分查找函数都定义在 <algorithm> 头文件中：

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

重要前提：使用这些函数前，必须确保序列是已排序的（默认升序）。如果序列未排序，结果是未定义的。

二、四大核心函数

C++标准库提供了四个主要的二分查找函数，它们分别解决不同的问题：

函数	返回值	使用场景
binary_search	bool	只需要知道元素是否存在
lower_bound	迭代器	查找第一个 ≥ 目标值的位置
upper_bound		查找第一个 > 目标值的位置
equal_range	pair 迭代器对	需要获取所有等于目标值的范围

1. binary_search：判断元素是否存在

当只需要知道一个值是否在序列中时，binary_search 是最直接的选择：

std::vector<int> nums = {1, 3, 5, 7, 9, 11};

// 查找元素是否存在
if (std::binary_search(nums.begin(), nums.end(), 7)) {
    std::cout << "找到了 7！" << std::endl;
}

// 查找不存在的元素
if (!std::binary_search(nums.begin(), nums.end(), 4)) {
    std::cout << "4 不在数组中" << std::endl;
}

特点：

• 返回 bool 类型，只回答"有没有"
• 如果需要知道位置，请使用其他函数
• 时间复杂度 O(log n)

2. lower_bound：查找第一个≥目标的位置

lower_bound 返回第一个大于等于目标值的元素位置：

std::vector<int> nums = {1, 3, 5, 5, 5, 7, 9};

// 查找第一个 >= 5 的位置
auto it = std::lower_bound(nums.begin(), nums.end(), 5);
int index = it - nums.begin();  // 输出: 2 (第一个5的位置)

// 查找一个不存在的值
auto it2 = std::lower_bound(nums.begin(), nums.end(), 6);
int index2 = it2 - nums.begin();  // 输出: 5 (指向7的位置)

// 查找比所有元素都大的值
auto it3 = std::lower_bound(nums.begin(), nums.end(), 10);
if (it3 == nums.end()) {
    std::cout << "没有元素 >= 10" << std::endl;
}

关键理解：

• 如果目标存在，返回第一个匹配位置
• 如果目标不存在，返回第一个大于目标的位置
• 如果所有元素都小于目标，返回 end()

3. upper_bound：查找第一个>目标的位置

upper_bound 返回第一个大于目标值的元素位置：

std::vector<int> nums = {1, 3, 5, 5, 5, 7, 9};

// 查找第一个 > 5 的位置
auto it = std::upper_bound(nums.begin(), nums.end(), 5);
int index = it - nums.begin();  // 输出: 5 (指向7的位置)

// 对于不存在的值，upper_bound 和 lower_bound 结果相同
auto it_lower = std::lower_bound(nums.begin(), nums.end(), 6);  // 指向7
auto it_upper = std::upper_bound(nums.begin(), nums.end(), 6);  // 指向7
// 两者相同，因为6不在数组中

4. equal_range：获取整个相等区间

equal_range 返回一个 pair，包含 lower_bound 和 upper_bound 的结果，表示所有等于目标值的元素范围：

std::vector<int> nums = {1, 3, 5, 5, 5, 7, 9};

// 获取所有等于5的范围
auto range = std::equal_range(nums.begin(), nums.end(), 5);

// range.first 指向第一个5 (lower_bound)
// range.second 指向7 (upper_bound)
int firstIndex = range.first - nums.begin();   // 2
int lastIndex = range.second - nums.begin() - 1; // 4

// 判断元素是否存在：如果区间非空，则存在
if (range.first != range.second) {
    std::cout << "找到了 " << (range.second - range.first) << " 个元素" << std::endl;
}

// 遍历所有等于目标值的元素
for (auto it = range.first; it != range.second; ++it) {
    std::cout << *it << " ";  // 输出: 5 5 5
}

三、实战案例

案例1：统计元素出现次数

利用 upper_bound - lower_bound 可以高效统计重复元素个数：

std::vector<int> nums = {1, 2, 2, 2, 3, 4, 4, 5};
int target = 2;

// 统计 target 出现的次数
int count = std::upper_bound(nums.begin(), nums.end(), target) 
          - std::lower_bound(nums.begin(), nums.end(), target);

std::cout << "2 出现了 " << count << " 次" << std::endl;  // 输出: 3

案例2：有序插入保持顺序

使用 lower_bound 找到插入位置，可保持数组有序：

std::vector<int> nums = {1, 3, 5, 7, 9};
int newValue = 6;

// 找到第一个 >= 6 的位置
auto pos = std::lower_bound(nums.begin(), nums.end(), newValue);
nums.insert(pos, newValue);

// 结果: {1, 3, 5, 6, 7, 9}

案例3：查找离目标最近的数

结合 lower_bound 和边界判断：

std::vector<int> nums = {1, 3, 6, 8, 10};
int target = 5;

auto it = std::lower_bound(nums.begin(), nums.end(), target);
int closest;

if (it == nums.begin()) {
    closest = *it;
} else if (it == nums.end()) {
    closest = *(it - 1);
} else {
    int a = *it;
    int b = *(it - 1);
    closest = (abs(a - target) < abs(b - target)) ? a : b;
}

std::cout << "离 5 最近的数是: " << closest << std::endl;  // 输出: 6

案例4：LeetCode 实战（统计正负数个数）

来自 LeetCode 的题目，使用二分查找实现 O(log n) 解法：

class Solution {
public:
    int maximumCount(std::vector<int>& nums) {
        // 负数个数：第一个 >= 0 的位置
        int neg = std::lower_bound(nums.begin(), nums.end(), 0) - nums.begin();
        
        // 正数个数：第一个 > 0 的位置到末尾
        int pos = nums.end() - std::upper_bound(nums.begin(), nums.end(), 0);
        
        return std::max(neg, pos);
    }
};

四、自定义比较函数

默认情况下，这些函数使用 < 进行比较。对于自定义类型或特殊排序规则，可以提供自定义比较函数：

struct Person {
    std::string name;
    int age;
};

// 按年龄排序
std::vector<Person> people = {{"Alice", 25}, {"Bob", 30}, {"Charlie", 35}};

// 按年龄比较的谓词
auto compareByAge = [](const Person& a, const Person& b) {
    return a.age < b.age;
};

// 查找第一个年龄 >= 28 的人
int targetAge = 28;
auto it = std::lower_bound(people.begin(), people.end(), targetAge,
    [](const Person& p, int age) {
        return p.age < age;
    }
);

五、函数选择指南

根据你的需求选择合适的函数：

你想知道	使用函数
值是否存在？	binary_search
存在的话，位置在哪？	equal_range
第一个 ≥ 值的位置？	lower_bound
第一个 > 值的位置？	upper_bound
有多少个等于该值？	equal_range + distance
想要插入并保持顺序？	lower_bound 找插入点

选择原则：在有序区间中，优先使用这些二分查找函数而非线性查找（如 std::find），因为它们的 O(log n) 复杂度在大数据量下优势明显。

六、注意事项

1. 前提条件：序列必须已排序，否则结果是未定义的

2. 等价 vs 相等：二分查找使用"等价"概念（!(a < b) && !(b < a)），而非 operator==。这与关联容器的行为一致

3. 迭代器要求：这些函数需要随机访问迭代器，适用于 vector、deque、array，但不适用于 list（虽然能编译，但会退化为线性时间）

4. 关联容器：对于 set/map，应使用它们的成员函数（如 set::find），它们通常比通用算法更高效

七、性能对比

数据规模	线性查找 (find)	二分查找 (binary_search)
10	~10 次比较	~4 次比较
1000	~1000 次比较	~10 次比较
1,000,000	~1,000,000 次比较	~20 次比较

对于一个有 1000 个元素的序列，二分查找可能比线性查找快 200 倍。

总结

C++ 标准库提供的二分查找函数族，覆盖了从简单的存在性检查到复杂的区间查找的各种场景。掌握它们，可以：

• 避免手写二分查找的各种边界错误
• 写出更简洁、可读性更强的代码
• 享受标准库经过优化的性能

记住这四个核心函数：binary_search、lower_bound、upper_bound、equal_range，它们将是你处理有序序列时的得力助手。