C++ upper_bound()和lower_bound()（二分查找中使用）的定义，使用方法和区别

C++ upper_bound()和lower_bound()是涉及二分查找问题一个很好用的工具，熟练使用就不用为二分查找的边界发愁了（不用重复造轮子了）

1. 调用方式

upper_bound有两种调用方式：

template <class ForwardIterator, class T>  
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);
1
2

template <class ForwardIterator, class T, class Compare>  
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
1
2

注意：

1. 前两个参数是ForwardIterator 类型（这个一般比较容易满足，各种RandomAccessIterator都满足，而最常见的对vector排序，vector的迭代器就是RandomAccessIterator，参见：各种iterator之间的关系
2. 如果采用自定义比较函数，传入的是对象而不是类名！！这个和构建一些有序的数据结构，如priority_queue，map，set等不一样，一般这些传入的是类名而不是一个对象！（举个例子，sort中的comp可以传入greater()，而不能是greater，见下文），其中涉及到函数对象的知识，可以参考：C++ 函数对象（Function Object）是什么？
   而对于构建priority_queue，这里传入的就是类名，而不是一个对象！

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;
1
2
3
4
5

同样的对于lower_bound来说也是如此：

template <class ForwardIterator, class T>  
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);
1
2

template <class ForwardIterator, class T, class Compare>  
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
1
2

2. upper_bound()和lower_bound()定义和区别

定义

文档中的关于upper_bound()和lower_bound()的介绍值得深入细读：
以下来自官方文档：
upper_bound()

1. 返回指向范围[first,last)中第一个元素使得value < element（或comp(value，element）)为true（即严格大的迭代器），如果找不到这样的元素，则为last。
2. [first,last)必须根据表达式!（value < element）或!comp（value，element）进行分区，即表达式为true的所有元素必须在表达式为false的所有元素之前！完全排序的[first,last)符合此条件。
3. 如果没有自定义比较函数就使用operator<来比较element，如果自定义了比较函数就使用comp来比较element

lower_bound()

1. 返回指向范围[first,last)中的第一个元素使得该元素不满足element< value（或comp(element，value）为false)、（即大于或等于）的迭代器，如果找不到这样的元素，则返回last。

2. [first,last)必须相对于表达式element< value（或comp(element，value）)进行分区，即表达式为true的所有元素必须在表达式为false的所有元素之前。完全排序的[first,last)符合此条件。

3. 如果没有自定义比较函数就使用operator<来比较element，如果自定义了比较函数就使用comp来比较element

2.1 lower_bound：

Returns an iterator pointing to the first element in the range [first, last) that does not satisfy element < value (or comp(element, value)), (i.e. greater or equal to), or last if no such element is found.

这里的value就是模板里的val，element就是要比较的元素

注意：在C++比较过程中，A less than B（A < B），表示按照“从小到大”（可以自定义）排序的话，A应该放在B前面。
所以这里does not compare less than val就是greater或者equal to val的含义，也就是lower_bound返回 [first, last) 第一个不满足element < value（或者不满足comp(element, value)）的元素的iterator，如果都不满足，则返回last这个iterator

注意：
1.

The range [first, last) must be partitioned with respect to the expression element < value (or comp(element, value)), i.e., all elements for which the expression is true must precede all elements for which the expression is false. A fully-sorted range meets this criterion.

也就是如果从大到小排序（greater），但是却用从小到大中以及最大的值作为比较函数，是查不到第一个元素的，而是返回last。
举例如下：

vector<int> vec = {1, 2, 3, 4, 5, 6};
// 从大到小排序
// greater必须加上()因为需要传入一个对象
sort(vec.begin(), vec.end(), greater<int>()); 
// 以默认的从小到大作为比较函数以及最大的值（此为6）作为value
auto iter = lower_bound(vec.begin(), vec.end(), 6);
1
2
3
4
5
6

这里返回的iter就是vec.end()，因为所有没有任何元素满足element < 6。
2. comp(element, value)，第二个参数才是value！！

举例：对于自定义比较函数：

#include      // std::cout
#include     // std::lower_bound
#include        // std::vector
using namespace std;
//以普通函数的方式定义查找规则
bool mycomp(int i,int j) { return i>j; }

//以函数对象的形式定义查找规则
class mycomp2 {
public:
    bool operator()(const int& i, const int& j) {
        return i > j;
    }
};

int main() {
    int a[5] = { 1,2,3,4,5 };
    //从 a 数组中找到第一个不小于 3 的元素
    int *p = lower_bound(a, a + 5, 3);
    cout << "*p = " << *p << endl;

    vector<int> myvector{ 4,8, 9, 5,3,1,7, 2 };
    //根据 mycomp2 规则，从 myvector 容器中找到第一个违背 mycomp2 规则的元素
    vector<int>::iterator iter = lower_bound(myvector.begin(), myvector.end(),3,mycomp2());
    cout << "*iter = " << *iter;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

输出的结果：

*p = 3
*iter = 3
1
2

在第二个例子中，3前面所有的元素都是大于3的，后面所有的元素都是小于3

2.2 upper_bound()

注意要点：

1. comp（value，element）,第一个参数就是value！！
   举例如下：

#include      // std::cout
#include     // std::upper_bound
#include        // std::vector
using namespace std;
//以普通函数的方式定义查找规则
bool mycomp(int i, int j) { return i > j; }
//以函数对象的形式定义查找规则
class mycomp2 {
public:
    bool operator()(const int& i, const int& j) {
        return i > j;
    }
};
int main() {
    int a[5] = { 1,2,3,4,5 };
    //从 a 数组中找到第一个大于 3 的元素
    int *p = upper_bound(a, a + 5, 3);
    cout << "*p = " << *p << endl;
    vector<int> myvector{ 4,5,3,1,2 };
    //根据 mycomp2 规则，从 myvector 容器中找到第一个违背 mycomp2 规则的元素
    vector<int>::iterator iter = upper_bound(myvector.begin(), myvector.end(), 3, mycomp2());
    cout << "*iter = " << *iter;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

输出：

*p = 4
*iter = 1
1
2

在实际情况中，我们遇到的最多的就是给定从小到大排序好的数组，找出第一个大于某个元素或者大于等于某个元素的位置，找出第一个大于某个元素的位置就是用的upper_bound()，找出大于等于某个元素的位置就是lower_bound()，更复杂的情况就需要借助自定义的比较函数了。

参考资料：

1. https://en.cppreference.com/w/cpp/algorithm/upper_bound
2. https://en.cppreference.com/w/cpp/algorithm/lower_bound
3. 代码案例部分来自于C语言中文网