查找算法：find、binary_search、lower_bound与upper_bound
极难5语言版本：通用
概述：学会在数据中找到特定元素，从最简单的逐个找（find）到高效的二分查找，以及找到边界位置。
查找算法：find、binary_search、lower_bound 与 upper_bound —— 在数据中精准定位
同学们好！今天我们来学习编程中非常重要的一个技能——查找。想象一下，你有一千本漫画书，要找出《海贼王》第100卷在哪里，或者想知道《名侦探柯南》第50卷在书架上的什么位置。这类问题在编程里就是“查找算法”的工作。
STL（标准模板库）提供了几种查找工具，它们各有各的绝活。就像你查字典，有时候要一页一页翻（find），有时候知道按拼音顺序可以快速翻（binary_search），还有时候要知道某个字第一次出现和最后一次出现的位置（lower_bound 和 upper_bound）。下面我们一个一个来认识它们。
1. 从生活中的例子引入
场景一：找一张CD
你有个CD架，上面摆满了各种CD，顺序是乱的。你要找周杰伦的《七里香》。最简单的方法是什么？从第一张开始一张一张地看，直到看到《七里香》。这就是 线性查找（find）。
场景二：在按拼音排好的书架上找书
你家书架上的书是按书名拼音顺序排好的（比如 A 开头的在左边，Z 开头的在右边）。你想找《西游记》。你会：
- 先看书架中间那本书，比如是《三国演义》（拼音 S）。
- 因为《西游记》拼音是 X，比 S 大，所以你去右边半段找。
- 再找右边半段中间，比如是《水浒传》（拼音 S），又比 X 小？等等，其实 X 比 S 大，但《水浒传》拼音也是 S？不对，假设我们按严谨拼音排，A→Z。那么你不断对半缩小范围，很快就能找到。这就是 二分查找（
binary_search等）。
场景三：在点名册里找姓“王”的所有同学
老师有一本按姓氏拼音排好的点名册。想知道姓“王”的同学有多少个，以及他们从第几个开始到第几个结束。这时你需要找到 第一个姓“王”的同学（lower_bound）和 第一个姓“王”之后的其他姓的同学（upper_bound），两个位置之间的就是所有姓“王”的同学。
2. 查找算法的原理和使用方法
2.1 find —— 线性查找（挨个找）
概念：find 就像在操场上一个一个地问：“是你吗？是你吗？”它从容器开头跑到结尾，找到第一个和目标值相等的元素，返回一个指针（迭代器）。如果找不到，就返回结束位置的指针。
- 复杂度：O(n)，n 是元素个数。n 很大时（比如上百万）会很慢。
- 优点：不要求数据有序，什么容器都能用。
- 缺点：数据量大时效率低。
生活中的例子：你有一篮混合水果（苹果、香蕉、橘子……随便放的），让你找出第一个葡萄。你就从篮子里一个一个拿出来看，直到看到葡萄。
C++ 代码示例：
#include <iostream>
#include <vector>
#include <algorithm> // 使用 find
using namespace std;
int main() {
// 一个混合水果篮，顺序随意
vector<string> fruit_basket = {"apple", "banana", "orange", "grape", "pear"};
// 在篮子中查找 "grape"
auto it = find(fruit_basket.begin(), fruit_basket.end(), "grape");
if (it != fruit_basket.end()) {
cout << "找到葡萄了！它在第 " << (it - fruit_basket.begin()) + 1 << " 个位置。" << endl;
} else {
cout << "篮子里没有葡萄。" << endl;
}
// 如果查找一个不存在的 "watermelon"
it = find(fruit_basket.begin(), fruit_basket.end(), "watermelon");
if (it == fruit_basket.end()) {
cout << "没有西瓜哦。" << endl;
}
return 0;
}
Python 等价：用 list.index() 或循环。
fruit_basket = ["apple", "banana", "orange", "grape", "pear"]
try:
idx = fruit_basket.index("grape")
print(f"找到葡萄了，位置: {idx + 1}")
except ValueError:
print("没有葡萄。")
2.2 binary_search —— 二分查找（快速判断有没有）
概念：binary_search 使用“二分法”快速判断一个值是否在有序数组中。它像猜数字游戏：你猜一个数，对方告诉你太大还是太小，直到猜中。每次排除一半的数据，所以非常快。
- 复杂度：O(log n)。n=1000时，只需要10次比较；n=100万时，只要20次。
- 前提：数据必须是 有序的（从小到大或自定义顺序）。如果数据没排序，结果会错误（通常是找不到，或者找到错误位置）。
- 返回值：只有
true或false，告诉你“存在”还是“不存在”，不告诉你位置！
生活中的例子：电话号码本按姓氏拼音排好，你想知道有没有“张三”这个人。你直接翻到中间，看姓氏是“李”还是“王”，然后决定往左还是往右，很快就能确定。
C++ 代码示例：
#include <iostream>
#include <vector>
#include <algorithm> // binary_search
using namespace std;
int main() {
// 有序数组（必须排好序）
vector<int> scores = {60, 70, 75, 80, 85, 90, 95, 100};
// 检查 85 分是否存在
bool has85 = binary_search(scores.begin(), scores.end(), 85);
if (has85) {
cout << "85分有人考到！" << endl;
} else {
cout << "没有85分。" << endl;
}
// 检查 86 分
bool has86 = binary_search(scores.begin(), scores.end(), 86);
cout << "86分是否存在？" << (has86 ? "存在" : "不存在") << endl;
return 0;
}
Python 等价：使用 bisect 模块的 bisect_left 来判断。
import bisect
scores = [60, 70, 75, 80, 85, 90, 95, 100]
def exists(arr, val):
idx = bisect.bisect_left(arr, val)
return idx < len(arr) and arr[idx] == val
print(f"85分存在吗？{exists(scores, 85)}")
print(f"86分存在吗？{exists(scores, 86)}")
常见错误：忘记了排序！ 如果 scores 没排序，比如 [80, 60, 100, 70]，那么 binary_search(scores.begin(), scores.end(), 70) 可能返回 false（因为二分法在无序数据中会迷失方向）。一定要先排序！
2.3 lower_bound 和 upper_bound —— 二分查找+位置（边界查找）
概念：这两个函数也是在有序区间上使用的。它们返回一个 迭代器（位置），告诉你某个值该放在哪里才不破坏顺序。
lower_bound(first, last, val)：返回值是 第一个 >= val 的元素的位置。通俗说：假如要把 val 插入有序数组中，并且尽量往左边插（不破坏顺序），那么lower_bound就是“第一个可以插入的位置”。upper_bound(first, last, val)：返回值是 第一个 > val 的元素的位置。也就是“最后一个可以插入的位置的下一个”。
为什么有两个？ 因为当数组中有重复元素时，我们需要知道重复元素的起始和结束位置。例如：
- 数组
[1, 2, 2, 2, 3, 4]中，查找2：lower_bound(2)返回指向第一个2（索引 1）。upper_bound(2)返回指向第一个大于2的元素，即3（索引 4）。- 那么从索引 1 到 3（共 4-1=3 个）就是所有
2的位置。
复杂度：O(log n) 前提：有序。
生活中的例子：全班同学按身高从矮到高排好队。老师喊：“身高1.5米的同学请出列！”
- 身高刚好1.5米的同学不止一个，老师需要知道 第一个1.5米的人（
lower_bound）是谁，以及 第一个超过1.5米的人（upper_bound）是谁。这两个位置之间的所有同学就是身高1.5米的人。
C++ 代码示例：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// 全班同学的身高（按从矮到高排好）
vector<double> heights = {1.2, 1.3, 1.5, 1.5, 1.5, 1.6, 1.7};
double target = 1.5;
// lower_bound: 第一个 >=1.5 的人
auto low = lower_bound(heights.begin(), heights.end(), target);
// upper_bound: 第一个 >1.5 的人
auto up = upper_bound(heights.begin(), heights.end(), target);
int first_pos = low - heights.begin();
int last_pos = up - heights.begin();
cout << "第一个身高1.5米的同学在第 " << first_pos + 1 << " 位" << endl;
cout << "第一个高于1.5米的同学在第 " << last_pos + 1 << " 位" << endl;
cout << "所以有 " << last_pos - first_pos << " 位同学身高恰好是1.5米" << endl;
// 如果目标身高不在数组中，比如 1.4
low = lower_bound(heights.begin(), heights.end(), 1.4);
if (low == heights.end()) {
cout << "所有同学都小于1.4米？不对，这里说明没有 >=1.4 的人？" << endl;
} else {
// 结果: 1.4 不存在，lower_bound 返回第一个 > 1.4 的元素，即 1.5
cout << "lower_bound(1.4) 指向身高 " << *low << "，索引 " << low - heights.begin() << endl;
}
// 如果目标比所有人都大，比如 2.0
low = lower_bound(heights.begin(), heights.end(), 2.0);
if (low == heights.end()) {
cout << "所有人身高都小于2.0米，lower_bound 返回 end" << endl;
}
return 0;
}
Python 等价：用 bisect_left 和 bisect_right。
import bisect
heights = [1.2, 1.3, 1.5, 1.5, 1.5, 1.6, 1.7]
target = 1.5
low = bisect.bisect_left(heights, target)
up = bisect.bisect_right(heights, target)
print(f"第一个1.5米位置: {low+1}")
print(f"第一个高于1.5米位置: {up+1}")
print(f"人数: {up - low}")
常见错误：
- 在无序数组上用 —— 结果完全错误。
- 忘记区分 lower 和 upper —— 新手常误以为
lower_bound返回的是等于值的第一个位置，实际上如果值不存在，它返回的是“第一个大于的值的位置”。例如[1, 3, 5]中lower_bound(2)返回指向3的迭代器，而不是end。 - 对返回值直接解引用 —— 如果返回
end()，解引用会导致程序崩溃。一定要先检查是否等于end()。
3. 常见错误与避坑指南
3.1 忘记排序就使用二分查找
vector<int> nums = {5, 1, 3, 8, 2};
bool found = binary_search(nums.begin(), nums.end(), 3); // 可能返回 false！
解决方法：先 sort(nums.begin(), nums.end());。
3.2 混淆 binary_search 和 find 的返回值
binary_search 返回 bool，不能直接得到位置；而 find 返回迭代器。如果想知道位置，用 lower_bound 或 find。
3.3 在 list 或 forward_list 上使用二分查找
二分查找要求随机访问迭代器，而 list 是双向迭代器，不支持 +、- 等操作。不能对 list 使用 lower_bound 等二分函数（虽然 find 可以用，因为 find 只需要输入迭代器）。
3.4 在自定义比较函数时忘记统一
如果你用 greater<int>() 排序（从大到小），那么二分查找也必须使用同样的比较函数：
sort(v.begin(), v.end(), greater<int>()); // 降序
auto it = lower_bound(v.begin(), v.end(), val, greater<int>());
否则结果不对。
3.5 认为 lower_bound 一定找到等于 val 的元素
实际上，即使 val 不存在，lower_bound 也会返回一个有效位置（指向第一个大于 val 的元素）。你需要手动判断 *it == val 才能确认是否存在。
4. 完整可运行的 C++ 示例（综合）
下面是一个模拟“图书馆找书”的程序，演示四种查找方法。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int main() {
// 图书馆里书架上的书名（按拼音顺序排好）
vector<string> books = {"bian cheng", "C++ primer", "hai zei wang",
"hong lou meng", "san guo yan yi", "shui hu zhuan",
"xi you ji", "yuan shi"};
// 1. 用 find 线性查找“西游记”
string target = "xi you ji";
auto it = find(books.begin(), books.end(), target);
if (it != books.end()) {
cout << "find: 找到了《" << target << "》，在书架的 "
<< (it - books.begin()) + 1 << " 号位置。" << endl;
} else {
cout << "find: 没找到" << endl;
}
// 2. 用 binary_search 检查“三国演义”是否存在
bool exists = binary_search(books.begin(), books.end(), "san guo yan yi");
cout << "binary_search: 三国演义" << (exists ? " 存在" : " 不存在") << endl;
// 3. 用 lower_bound 找第一个 >= "shui hu" 的书（即水浒传）
auto low = lower_bound(books.begin(), books.end(), "shui hu");
if (low != books.end()) {
cout << "lower_bound(\"shui hu\") 指向《" << *low << "》，索引 "
<< low - books.begin() << endl;
} else {
cout << "lower_bound 返回 end，说明所有书都小于 \"shui hu\"" << endl;
}
// 4. 用 upper_bound 找第一个 > "shui hu" 的书
auto up = upper_bound(books.begin(), books.end(), "shui hu");
if (up != books.end()) {
cout << "upper_bound(\"shui hu\") 指向《" << *up << "》，索引 "
<< up - books.begin() << endl;
} else {
cout << "upper_bound 返回 end" << endl;
}
// 5. 如果书很多，还可以用 equal_range 一次获得 lower 和 upper
auto range = equal_range(books.begin(), books.end(), "shui hu");
cout << "equal_range 返回: low=" << range.first - books.begin()
<< ", up=" << range.second - books.begin() << endl;
return 0;
}
运行结果示例：
find: 找到了《xi you ji》，在书架的 7 号位置。
binary_search: 三国演义 存在
lower_bound("shui hu") 指向《shui hu zhuan》，索引 5
upper_bound("shui hu") 指向《xi you ji》，索引 6
equal_range 返回: low=5, up=6
5. Python 完整示例（对应）
import bisect
# 书名列表（拼音顺序）
books = ["bian cheng", "C++ primer", "hai zei wang",
"hong lou meng", "san guo yan yi", "shui hu zhuan",
"xi you ji", "yuan shi"]
# 1. 用 index 线性查找
target = "xi you ji"
try:
idx = books.index(target)
print(f"find: 找到了《{target}》，位置 {idx+1}")
except ValueError:
print("find: 没找到")
# 2. 用 bisect 做二分查找判断存在性
def exists(arr, val):
i = bisect.bisect_left(arr, val)
return i < len(arr) and arr[i] == val
print(f"binary_search: 三国演义 { '存在' if exists(books, 'san guo yan yi') else '不存在' }")
# 3. lower_bound 和 upper_bound
low = bisect.bisect_left(books, "shui hu")
up = bisect.bisect_right(books, "shui hu")
print(f"lower_bound('shui hu') 索引 {low}, 元素 {books[low] if low < len(books) else '超出'}")
print(f"upper_bound('shui hu') 索引 {up}, 元素 {books[up] if up < len(books) else '超出'}")
6. 总结一览表
| 算法 | 返回值 | 是否要求有序 | 时间复杂度 | 用途 |
|---|---|---|---|---|
find | 迭代器（位置或 end） | 否 | O(n) | 在任何容器里找第一个等于目标的值 |
binary_search | bool | 是 | O(log n) | 快速判断目标是否存在 |
lower_bound | 迭代器（第一个 >= 目标） | 是 | O(log n) | 找到插入位置或重复区域起点 |
upper_bound | 迭代器（第一个 > 目标） | 是 | O(log n) | 找到重复区域终点 |
equal_range | pair(lower, upper) | 是 | O(log n) | 一次获得上下界 |
7. 相关知识点指引
如果你想继续深入学习，可以看看这些内容：
- 排序算法：
sort、stable_sort—— 二分查找的前提是数据有序，所以排序很重要。 - 迭代器：理解输入迭代器（
find可用）、随机访问迭代器（二分查找需要），能帮你避免在错误容器上使用。 - 自定义比较函数：在排序和查找中传入自定义规则，例如按字符串长度排序、按年龄排序等。
set和map：这些容器内部就是有序的，并且自带了find和count方法，底层也是二分查找（红黑树实现）。对于需要频繁查找的情况，用set或map可能更方便。lower_bound在set和map中的使用：它们是成员函数，只需要传入值即可，不需要传入整个区间。
同学们，查找算法是编程中最常用的基本功。从今天起，当你需要在一堆数据里找东西时，先想想：数据有序吗？我要找位置还是只想知道有没有？ 选对算法，你的程序就会又快又稳！加油！
例题精讲
1单选题
对于一个有序的 std::list<int> 容器，以下关于使用 std::binary_search 查找元素 5 的说法正确的是？
A可以正常使用，binary_search 只要求序列有序，与迭代器类型无关
B不能使用，因为 binary_search 需要随机访问迭代器，而 list 的迭代器是双向的
C可以使用，但会退化为线性查找，效率与 find 相同
D不能使用，因为 list 的元素存储不连续，无法进行二分查找
2判断题
对于有序序列，std::lower_bound 返回第一个不小于给定值的迭代器，std::upper_bound 返回第一个大于给定值的迭代器。因此，若序列中存在元素值等于 val，则区间 [lower_bound, upper_bound) 包含了所有等于 val 的元素。
3填空题
给定一个已排序的 vector<int> v = {1, 3, 5, 5, 7}，请使用 STL 函数找出第一个大于等于 5 的元素的下标（从 0 开始）。补全以下代码：
int pos = ___ - v.begin();
cout << pos; // 期望输出 24单选题
对于一个已排序的 std::vector<int>，若要在其中查找元素 10，以下哪种说法正确？
A使用 std::find 比 std::binary_search 更快
B使用 std::binary_search 比 std::find 更快
C两者的时间复杂度相同，性能相近
Dstd::find 在有序序列上会自动使用二分查找
5填空题
给定一个已排序的 vector<int> v = {1, 2, 2, 2, 3, 4}，请用一行代码统计目标值 target = 2 出现的次数。补全以下代码：
int cnt = ___;
cout << cnt; // 期望输出 3