如何正确食用 STL 自带二分

· · 算法·理论

前言

众所周知，二分是一种很常用的算法，常用于查找元素、逼近答案。但是，个人写的二分经常会出现奇奇怪怪的问题（RE、死循环等），所以在这里介绍几个 STL 自带的二分函数（包含在 <algorithm> 头文件中），让你考试时不再为此烦恼。

upper_bound

此函数用于查找一个有序数组或容器中第一个大于 x 的元素（其中 x 是输入的参数），并返回指向它的迭代器。

upper_bound 的原型如下：

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

其中第一个参数是被查找的容器的 begin 迭代器，第二个参数是 end 迭代器，第三个参数是上文所述的 x，第四个参数是类似 sort 函数的 Compare 比较函数，若不填则默认为 less<>()，即查找第一个大于 x 的元素；如果查找小于等于 x 的第一个元素，那么就填上 greater<>() 即可。

但要注意，如果不保证输入的初始数组是有序的，那么一定要对其进行排序！笔者曾经考试时因为题目描述不清楚，未对数组排序，使用了 upper_bound 函数，结果 80\rightarrow 0，立马从榜二掉到了榜十三。

例如，我们有一个数组 a=\{1,2,3,5,8,13\}，想要查找第一个大于等于 9 的元素，并返回它的值和下标，我们可以这么做：

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  int a[6]={1,2,3,5,8,13};
  auto i=upper_bound(a,a+6,9); // auto 为万能指针，现在它是一个迭代器
  cout<<i-a<<endl; // 获取下标
  cout<<*i<<endl; // 获取元素值
  return 0;
/*
如果是用 vector 等 STL 自带容器，那么它的用法是这样的：
  vector<int> a={1,2,3,5,8,13};
  auto i=upper_bound(a.begin(),a.end(),9);
  cout<<i-a.begin()<<endl;
  cout<<*i<<endl;
*/
}

程序运行结果为：

5
13

值得一提的是，在 map、set、multimap 和 multiset 中，因为元素本来就是有序的，所以用法是这样的：

map<int,int> m;
m.emplace(21,21);
m.emplace(23,3);
auto i=m.upper_bound(22); // 假设要传入的值为 22

lower_bound

用法与 upper_bound 类似，只是其查找的是第一个大于等于 x 的元素。其它完全相同，请读者自行推导。

binary_search

此函数的功能是查找有序列表中是否出现元素 x。如果出现过，那么返回 true；否则返回 false。用法与 upper_bound 相似。

例如，要在数组 a=\{1,2,3,5,8\} 中查找数值 5，我们可以这么写：

#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
  int a[5]={1,2,3,5,8};
  puts(binary_search(a,a+5,8)?"Yes":"No");
  return 0;
}

程序运行结果为：

Yes

美中不足的是，此函数不能返回 x 所在的位置。如果需要查找位置还是使用 upper_bound 或 lower_bound 吧……

除了这三个二分函数，还有一个不是很常用的 equal_range() 函数（用来统计有序列表中所有数都等于 x 的半闭半开区间，返回值为迭代器 pair，first 和 second 分别存储区间的开始和结束）。有兴趣的同学可以自行了解。