【C++】 STL 二分查找算法

STL提供了find()、find_if()、search()等函数查找某个元素，使用的是顺序查找实现的，即逐个遍历直到找到满足条件的元素。
针对已经是有序的序列来说，STL提供了更高效的以二分查找实现的查找函数：lower_bound()、upper_bound()、equal_range()、binary_search()4个查找函数。

• lower_bound():在指定区域查找不小于目标值的第一个元素。
  upper_bound():在指定区间查找大于目标值的第一个元素。
  equal_range():在指定范围内查找等于目标值的所有元素。
  binary_search():在指定区域查找是否包含某个目标元素

函数声明

1. lower_bound()

ForwardIterator lower_bound(ForwardIterator first,ForwardIterator last,const T& val);
ForwardIterator lower_bound(ForwardIterator first,ForwardIterator last,const T& val,Compare comp);

参数comp指定自定义比较规则，接收包含2个形参（第2个形参值为val）的函数，该函数返回值为bool类型。
2. upper_bound()

ForwardIterator upper_bound(ForwardIterator first,Forward last,const T& val);
ForwardIterator upper_bound(ForwardIterator first,ForwardIterator last,const T& val,Compare comp);

参数comp指定自定义比较规则，接收包含2个形参（第1个形参值为val）的函数，该函数返回值为bool类型。

3. equal_range()

pair<ForwardIterator,ForwardIterator> equal_range(ForwardIterator first,forWardIterator last,const T& val);
pair<ForwardIterator,ForwardIterator> equal_range(ForwardIterator first,forWardIterator last,const T& val,Compare comp);

参数comp指定自定义比较规则，接收包含2个形参（第2个形参值为val）的函数，该函数返回值为bool类型。

4. binary_search()

bool binary_search(ForwardIterator first,ForwardIterator last,const T& val);
bool binary_search(ForwardIterator first,ForwardIterator last,const T& val,Compare comp);

参数comp指定自定义比较规则，接收包含2个形参（第1个形参值为val）的函数，该函数返回值为bool类型。

函数介绍

lower_bound()

在指定区域内查找不小于目标值的第一个元素。查找到的元素≥目标值。
返回值是正向迭代器，查找成功，指向找到的元素，否则指向和last相同。

upper_bound()

在指定区域查找大于目标值的第一个元素，查找到的元素>目标值。
返回值是正向迭代器，查找成功，指向找到的元素，否则，指向和last相同。

equal_range()

在指定区域内查找等于目标值的所有元素。
返回值是pair类型，包含2个正向迭代器，
查找成功时，第1个迭代器指向[first,last)区间内的第一个等于val的元素；第2个迭代器指向[first,last)区间中第一个大于val的元素。
查找失败，2个迭代器都指向大于val的第一个元素，或者和last迭代器指向相同。
equal_range()函数可以看作是lower_bound()和upper_bound()的合体。

binary_search()

查找指定区间内是否包含某个目标元素。
返回值是bool类型。如果成功找到和val相等的元素，返回true，否则返回false。

需要注意的是以上四个函数指定的区间内的序列是”已排好序“的序列。所谓已经排好序是指所有令 element < val成立的元素都位于不成立元素的前面，element是指定范围内的元素，比如序列{7,5,9,6,4,3,1,2}，当val=4的时候，这四个函数是可以成功运行的。