剑指信奥 | C++ 之 STL - 算法 bianry search
剑指信奥｜C++ 之 STL 算法 binary search
尽管二分查找的基本思想相对简单，但细节可以令人难以招架
lower_bound
今天，我们学习 STL 算法中的二分搜索 binary search 分类中的几个函数，关于什么是二分搜索，我们稍后再说。
首先学习的算法是 lower_bound()，这个函数的作用是返回指向范围 [first, last) 中首个不小于指定值为 value 的元素的迭代器，若找不到这种元素则返回 last。
基本的 lower_bound() 接收 3 个参数：
firstlastvalue
代码示例：
#include<iostream>
#include<algorithm>
#include<vector>
int main() {
// 初始化 vector
vector<int> vi = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
// 声明迭代器
vector<int>::iterator first, last, it;
// 初始化迭代器
first = vi.begin();
last = vi.end();
int value = 2;
// lower_bound 查找
it = lower_bound(first, last, value);
// 输出
for (auto i = first; i < it; ++i) {
cout << *i << " ";
}
return 0;
}
/*
output
0 1
*/
代码说明：
需要注意的是，lower_bound() 所针对的序列必须是在 [first, last) 范围内已排序的。
lower_bouond() 有重载的含有二元谓词比较器的函数，在此不再举例。
upper_bound
第二个算法是 upper_bound()，这个函数的作用是返回指向范围 [first, last) 中首个大于指定 value 的元素的迭代器，若找不到这种元素则返回 last。
这个函数与之前的 lower_bound() 是类似的。
基本的 upper_bound() 接收 3 个参数：
firstlastvalue
代码示例：
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
// 初始化 vector
vector<int> vi = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
// 声明迭代器
vector<int>::iterator first, last, it;
// 初始化迭代器
first = vi.begin();
last = vi.end();
int value = 2;
// upper_bound 查找
it = upper_bound(first, last, value);
// 输出
for (auto i = it; i < last; ++i) {
cout << *i << " ";
}
return 0;
}
/*
output
3 4 5 6 7 8 9
*/
代码说明：
同样需要注意的是，upper_bound() 所针对的序列必须是在 [first, last) 范围内已排序的。
upper_bouond() 也有重载的含有二元谓词比较器的函数，在此不再举例。
binary_search
函数 binary_search() 就是我们今天主题二分搜索的含义，在讲解这个函数作用之前，我们先来简单了解一下二分搜索。
在计算机科学中，二分查找算法（英语：binary search algorithm）是一种在有序数组中查找某一特定元素的搜索算法。
搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束。
如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
这种搜索算法每一次比较都使搜索范围缩小一半。
Wikipedia
看起来好像很复杂，其实原理比较简单：
二分搜索演算法 ｜ Wikipedia
二分搜索也叫折半查找，就是在一个有序的序列中查找一个元素，每次都从序列的中间开始，把要搜索的元素与中间值比较，不相同则开始下一次的折半，直到找到元素为止。
这个算法的提出早至 1946 年，虽然原理并不难，但是绝大多数的程序员很难在第一次就写出一份正确的代码。
这其中的原因有很多，主要问题来自于边界值的差一错误 Off-by-one error。
以至于图灵奖获得者高德纳在他的大作「计算机程序设计艺术」第三卷中如此描述二分搜索：尽管二分查找的基本思想相对简单，但细节可以令人难以招架 —
Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky
§6.2.1 The Art of Computer Programming 3
当然，我们现在是在学习 STL 中的 binary_search()，应用正确是不会有 bug 的，下面我们来看下这个算法的使用。
基本的 binary_search() 接收 3 个参数：
firstlastvalue
代码示例：
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
// 初始化 vector
vector<int> vi = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
// 声明迭代器
vector<int>::iterator first, last, it;
// 初始化迭代器
first = vi.begin();
last = vi.end();
int value = 2;
// binary_search 查找
cout << binary_search(first, last, value) << endl;
return 0;
}
/*
output
1
*/
代码说明：
binary_search() 返回值是 1 或 0，表示要查找的值存在与否。
这个函数也有关于比较函数的重载函数。
equal_range
函数 equal_range() 的作用是返回范围 [first, last) 中含有所有等价于 value 的元素的范围。
基本的 equal_range() 接收 3 个参数：
firstlastvalue
代码示例：
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
// 初始化 vector
vector<int> vi = {0, 1, 2, 3, 3, 3};
// 声明迭代器
vector<int>::iterator first, last, it;
// 初始化迭代器
first = vi.begin();
last = vi.end();
int value = 3;
// equal_range 查找
auto pair = equal_range(first, last, value);
// 输出
for (auto i = pair.first; i < pair.second; ++i) {
cout << *i << " ";
}
return 0;
}
/*
output
3 3 3
*/
代码说明：
equal_range() 返回的内容比较特别，pair 是一对迭代器，第一迭代器指向首个不小于 value 的元素，而第二迭代器指向首个大于 value 的元素。
所以我们可以使用 pair.first 和 pair.last 来输出我们要查找的元素。
以上就是 C++ STL 中关于二分查找的所有函数，虽然名字各不相同，但以上函数的内部实现都是二分查找。
binary_search() 和 equal_range() 内部都调用了 lower_bound() 和 upper_bound()，因此人们才将其归为一类。