剑指信奥｜C++ 之 STL 算法 binary search

尽管二分查找的基本思想相对简单，但细节可以令人难以招架

lower_bound

今天，我们学习 STL 算法中的二分搜索 binary search 分类中的几个函数，关于什么是二分搜索，我们稍后再说。

首先学习的算法是 lower_bound()，这个函数的作用是返回指向范围 [first, last) 中首个不小于指定值为 value 的元素的迭代器，若找不到这种元素则返回 last。

基本的 lower_bound() 接收 3 个参数：

1. first
2. last
3. value

代码示例：

#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 个参数：

1. first
2. last
3. value

代码示例：

#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 个参数：

1. first
2. last
3. value

代码示例：

#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 个参数：

1. first
2. last
3. value

代码示例：

#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()，因此人们才将其归为一类。