STL中的二分查找

二分查找是重要且常用的算法，在STL中自然少不了它的身影。本文介绍一下在STL中与二分查找有关的函数。

要注意，这些函数都要求集合是有序的，在使用之前应使用std::sort等函数对集合进行排序。

检查元素是否存在

std::binary_search用来检查指定的元素是否存在集合中，函数原型如下：

1
2
3
4
5
template< class ForwardIt, class T >
bool binary_search( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );

第一个原型使用<操作符来比较元素，第二个原型使用指定的比较器来比较元素。比较器的比较规则应该与排序时使用的比较规则一致。

使用示例如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//使用默认比较器来查找元素
std::vector<int> numbers{ 1, 3, 5, 7, 9 };
bool exist;
exist = std::binary_search(numbers.begin(), numbers.end(), 3); // exist = true
exist = std::binary_search(numbers.begin(), numbers.end(), 4); // exist = false

//使用自定义比较器来查找元素
auto comparer = [](int i1, int i2) {
    return i1 > i2;
};

std::sort(numbers.begin(), numbers.end(), comparer); // 9, 7, 5, 3, 1
exist = std::binary_search(numbers.begin(), numbers.end(), 5, comparer); //exist = true
exist = std::binary_search(numbers.begin(), numbers.end(), 6, comparer); //exist = false

std::binary_search至多需要进行log2(last - first) + O(1)次比较。

std::binary_search的使用场景比较单一，它只能知道某个元素是否存在集合中。如果要获取元素的位置，需要使用下面的函数。

获取元素位置

std::lower_bound

std::lower_bound用来获取集合中第一个不小于指定值的元素位置，函数原型如下：

1
2
3
4
5
template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );

第一个原型使用<操作符来比较元素，第二个原型使用指定的比较器来比较元素。比较器的比较规则应该与排序时使用的比较规则一致。

使用示例如下：

1
2
3
4
5
6
7
8
9
10
11
std::vector<int> numbers{ 1, 3, 5, 7, 9 };

std::vector<int>::iterator iterator;
iterator = std::lower_bound(numbers.begin(), numbers.end(), 3); 
// *iterator = 3

iterator = std::lower_bound(numbers.begin(), numbers.end(), 4); 
// *iterator = 5

iterator = std::lower_bound(numbers.begin(), numbers.end(), 11); 
// iterator = numbers.end()

要注意，std::lower_bound返回的迭代器指向的是第一个不小于（即等于或大于）指定值的元素，所以在它返回之后还要再检查一次，以确认真的找到了该元素。例如：

1
2
3
4
5
6
7
8
9
10
11
//获取集合
std::vector<int> numbers = ...; 

//查找元素位置
auto iterator = std::lower_bound(numbers.begin(), numbers.end(), 3); 
if (iterator != numbers.end() && *iterator == 3) {
    //集合中存在该元素，iterator指向它。
}
else {
    //集合中不存在该元素，iterator指向第一个大于它的元素，或集合末尾。
}

这样设计的好处是，如果要执行的是“如果元素不存在则插入”的操作，那么可以直接往iterator指向的位置插入新元素，而不必担心破坏集合的有序性。

std::lower_bound至多需要进行log2(last - first) + O(1)次比较。

std::upper_bound

与std::lower_bound类似，std::upper_bound用来获取集合中第一个大于指定值的元素位置，函数原型如下：

1
2
3
4
5
template< class ForwardIt, class T >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );

第一个原型使用<操作符来比较元素，第二个原型使用指定的比较器来比较元素。比较器的比较规则应该与排序时使用的比较规则一致。

使用示例如下：

1
2
3
4
5
6
7
8
9
10
11
std::vector<int> numbers{ 1, 3, 5, 7, 9 };

std::vector<int>::iterator iterator;
iterator = std::upper_bound(numbers.begin(), numbers.end(), 3); 
// *iterator = 5

iterator = std::upper_bound(numbers.begin(), numbers.end(), 4); 
// *iterator = 5

iterator = std::upper_bound(numbers.begin(), numbers.end(), 11); 
// iterator = numbers.end()

由于std::upper_bound返回的迭代器指向的是第一个大于指定值的元素，相对来说它的使用场景较std::lower_bound要少。

std::upper_bound至多需要进行log2(last - first) + O(1)次比较。

std::equal_range

std::equal_range用来获取集合中所有与指定值相等的元素范围，函数原型如下：

1
2
3
4
5
template< class ForwardIt, class T >
std::pair<ForwardIt,ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
std::pair<ForwardIt,ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value, Compare comp );

第一个原型使用<操作符来比较元素，第二个原型使用指定的比较器来比较元素。比较器的比较规则应该与排序时使用的比较规则一致。

std::equal_range返回一对迭代器，第一个迭代器指向第一个不小于指定值的元素（等同于std::lower_bound的返回值），第二个迭代器指向第一个大于指定值的元素（等同于std::upper_bound的返回值）。如果两个迭代器相等，说明不存在这样的元素。

使用示例如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
std::vector<int> numbers{ 1, 3, 5, 5, 7, 9 };

std::pair<std::vector<int>::iterator, std::vector<int>::iterator> iterator_pair;
iterator_pair = std::equal_range(numbers.begin(), numbers.end(), 3); 
// *iterator_pair.first = 3, *iterator_pair.second = 5(1)  括号中的数字表示是第几个，下同

iterator_pair = std::equal_range(numbers.begin(), numbers.end(), 5); 
// *iterator_pair.first = 5(1), *iterator_pair.second = 7

iterator_pair = std::equal_range(numbers.begin(), numbers.end(), 8); 
// *iterator_pair.first = *iterator_pair.second = 9

iterator_pair = std::equal_range(numbers.begin(), numbers.end(), 9); 
// *iterator_pair.first = 9, iterator_pair.second = numbers.end()

iterator_pair = std::equal_range(numbers.begin(), numbers.end(), 11); 
// iterator_pair.first = iterator_pair.second = numbers.end()

std::equal_range至多需要进行2 * log2(last - first) + O(1)次比较，在性能上不如std::lower_bound和std::upper_bound，所以如果不需要获取相等元素区间的话，按需调用std::lower_bound或std::upper_bound是更好的选择。