12、二分查找算法与有序区间合并
二分查找，说白了就是在一个有序序列里快速定位目标值。我刚开始学STL时觉得这玩意儿太简单了，不就是折半查找嘛。直到我在项目中遇到一个性能瓶颈——每天要处理上千万次区间查询，才发现自己根本不会用STL的二分工具。
嗯，这一章我们就把STL里跟二分查找相关的几个函数彻底讲透。包括binary_search、lower_bound、upper_bound、equal_range，还有有序区间的合并操作。最后我会带大家做一个实战项目：区间查询系统。
12.1 binary_search：你到底在不在？
binary_search是最简单的二分查找函数。它只告诉你一个答案：目标元素在不在序列里。返回true或false。
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {1, 3, 5, 7, 9, 11, 13};
bool found = std::binary_search(v.begin(), v.end(), 7);
std::cout << "7 " << (found ? "找到了" : "没找到") << std::endl;
found = std::binary_search(v.begin(), v.end(), 8);
std::cout << "8 " << (found ? "找到了" : "没找到") << std::endl;
return 0;
}输出结果：
7 找到了
8 没找到binary_search还有一个带比较器的重载版本，适用于自定义类型：
struct Person {
std::string name;
int age;
};
bool operator<(const Person& a, const Person& b) {
return a.age < b.age;
}
// 使用自定义比较器
std::vector<Person> people = {{"Alice", 25}, {"Bob", 30}, {"Charlie", 35}};
bool found = std::binary_search(people.begin(), people.end(),
Person{"", 30},
[](const Person& a, const Person& b) {
return a.age < b.age;
});12.2 lower_bound与upper_bound：找到边界
binary_search只能告诉你"在不在"，但很多时候我们需要知道"在哪儿"。这时候就要用lower_bound和upper_bound了。
lower_bound：返回第一个不小于目标值的位置（即 >= target）。
upper_bound：返回第一个大于目标值的位置（即 > target）。
我个人的记忆方法是：lower_bound是"下界"，upper_bound是"上界"。它们俩配合起来，就能精确描述目标值在有序序列中的范围。
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {1, 3, 3, 3, 5, 7, 9};
auto it_low = std::lower_bound(v.begin(), v.end(), 3);
auto it_up = std::upper_bound(v.begin(), v.end(), 3);
std::cout <= "第一个3的位置: " << (it_low - v.begin()) << std::endl;
std::cout << "最后一个3之后的位置: " << (it_up - v.begin()) << std::endl;
std::cout << "3出现的次数: " << (it_up - it_low) << std::endl;
return 0;
}输出结果：
第一个3的位置: 1
最后一个3之后的位置: 4
3出现的次数: 3这里有个容易踩的坑：如果目标值不存在，lower_bound和upper_bound返回的位置是一样的。比如在{1, 3, 5, 7}中查找4，两个函数都返回指向5的迭代器。
12.3 equal_range：一次搞定上下界
equal_range其实就是把lower_bound和upper_bound打包在一起。它返回一个pair，first是lower_bound的结果，second是upper_bound的结果。
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {1, 3, 3, 3, 5, 7, 9};
auto range = std::equal_range(v.begin(), v.end(), 3);
std::cout << "范围: [" << (range.first - v.begin())
<< ", " << (range.second - v.begin()) << ")" << std::endl;
// 遍历所有等于3的元素
for (auto it = range.first; it != range.second; ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}输出结果：
范围: [1, 4)
3 3 3我个人习惯是：如果只需要判断存在性，用binary_search；如果需要精确位置，用lower_bound/upper_bound；如果既要下界又要上界，直接用equal_range，省得写两次调用。
12.4 有序区间合并：merge与inplace_merge
合并两个有序序列，听起来简单，但STL提供了两种方式：merge和inplace_merge。
merge：把两个有序序列合并到一个新序列中。
inplace_merge：把同一个序列中两个相邻的有序段合并成一个有序段。
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
// merge示例
std::vector<int> v1 = {1, 3, 5, 7};
std::vector<int> v2 = {2, 4, 6, 8};
std::vector<int> result(v1.size() + v2.size());
std::merge(v1.begin(), v1.end(),
v2.begin(), v2.end(),
result.begin());
std::cout << "合并结果: ";
for (int x : result) std::cout << x << " ";
std::cout << std::endl;
// inplace_merge示例
std::vector<int> v = {1, 3, 5, 2, 4, 6};
auto mid = v.begin() + 3; // 前三个有序，后三个有序
std::inplace_merge(v.begin(), mid, v.end());
std::cout << "原地合并结果: ";
for (int x : v) std::cout << x << " ";
std::cout << std::endl;
return 0;
}输出结果：
合并结果: 1 2 3 4 5 6 7 8
原地合并结果: 1 2 3 4 5 612.5 实战：区间查询系统
好了，理论讲完了。我们来做点实际的。假设你有一个在线教育平台，需要查询某个分数段内的学生。数据量很大，每天几百万条记录。
我当年在做一个类似系统时，一开始用的是遍历+条件判断，结果慢得离谱。后来改用二分查找，性能提升了上百倍。
#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
#include <random>
struct Student {
std::string name;
int score;
bool operator<(const Student& other) const {
return score < other.score;
}
};
class ScoreQuerySystem {
private:
std::vector<Student> students;
public:
void addStudent(const Student& s) {
students.push_back(s);
}
// 必须先排序才能查询
void prepare() {
std::sort(students.begin(), students.end());
}
// 查询分数在 [low, high] 区间内的所有学生
std::vector<Student> queryRange(int low, int high) {
// 找到第一个分数 >= low 的学生
auto low_it = std::lower_bound(students.begin(), students.end(),
Student{"", low});
// 找到第一个分数 > high 的学生
auto high_it = std::upper_bound(students.begin(), students.end(),
Student{"", high});
return std::vector<Student>(low_it, high_it);
}
// 统计某个分数段的人数
int countInRange(int low, int high) {
auto range = std::equal_range(students.begin(), students.end(),
Student{"", low},
[](const Student& a, const Student& b) {
return a.score < b.score;
});
// 这里需要调整，因为equal_range只能查单个值
// 实际应该用lower_bound和upper_bound
auto low_it = std::lower_bound(students.begin(), students.end(),
Student{"", low});
auto high_it = std::upper_bound(students.begin(), students.end(),
Student{"", high});
return static_cast<int>(high_it - low_it);
}
};
int main() {
ScoreQuerySystem sys;
// 模拟数据
sys.addStudent({"Alice", 85});
sys.addStudent({"Bob", 92});
sys.addStudent({"Charlie", 78});
sys.addStudent({"David", 95});
sys.addStudent({"Eve", 88});
sys.addStudent({"Frank", 76});
sys.prepare();
// 查询80-90分的学生
auto result = sys.queryRange(80, 90);
std::cout << "80-90分的学生: ";
for (const auto& s : result) {
std::cout << s.name << "(" << s.score << ") ";
}
std::cout << std::endl;
// 统计人数
int count = sys.countInRange(80, 90);
std::cout << "80-90分的人数: " << count << std::endl;
return 0;
}输出结果：
80-90分的学生: Alice(85) Eve(88)
80-90分的人数: 212.6 知识体系总览
下面这张图总结了本章的核心知识点和它们之间的关系：
这张图把本章的知识点分成了三大块：查找类算法、合并类算法和实战应用。你可以看到，所有二分算法的前提都是序列有序。这也是为什么我在实战系统中先调用了prepare()进行排序。
好了，这一章的内容就到这里。二分查找看似简单，但用好了能解决很多实际问题。尤其是lower_bound和upper_bound这对组合，在区间查询、数据统计等场景下非常强大。下次遇到有序数据上的查找问题，别再用遍历了，试试STL的二分工具吧。
公众号:蓝海资料掘金营，微信deep3321