二分搜索/lower_bound/upper_bound
C++ STL 里实现了两个二分搜索,lower_bound和upper_bound,支持在已经排好序的并且有随机迭代器的容器上进行二分搜索。(事实上map、set、multimap、multiset容器通过成员函数也提供了lower_bound和upper_bound,语意是相同的,实现方式不同)
lower_bound 是返回[b, e)区间上首个大于等于x的元素的迭代器
upper_bound 是返回[b, e)区间上首个大于x的元素的迭代器
下闭上开,和STL里其他地方都是一致的,lower_bound返回的迭代器 p 保证 [p, e) 都是大于等于x的,而upper_bound返回的迭代器q保证[b, q)都是小于等于x的。
STL里的这俩函数基本上不能用在自定义的容器上,因为它们要求容器类型通过typdef定义了各种特定类型,我下面实现了两个替代品,只要求迭代器可以随机访问(即可以加减任意数,随机迭代器可以任意移动,顺序迭代器只能加1减1,链表就只有顺序迭代器),元素有小于运算(我特意把所有的比较都改写成了小于)
1 | // 返回[b,e) 区间上首个大于等于x的元素的迭代器 |
二分算法看上去简单,如果不注意是很容易出错的,我觉得主要要注意2点:
1)循环不变性,比如lower_bound,我们找[b,e) 区间上首个大于等于x,在进入循环前我们排除了元素不在[b,e)上的情况,那么在循环内修改b或e的时候就要保证,修改后,要找的元素仍然在[b,e)上,e是开区间的,不要不小心就把元素丢到外面去了。
2)循环能终结,比如我们让b=mid,会不会搜索范围并没有变小呢?一般有几种方式可以调整终结条件,一种就是改while条件,一种就是改mid的计算,mid在偶数大小区间是有两个数可以选择的,mid = b + (e-b)/2 或 mid = b + (e-b+1)/2
有时候序列是降序的怎么办?通过反向迭代器
有时候我们想在一个范围内找满足某个条件的最大值或最小值
1 | // f满足存在一个k值得对于i<k有f(i)=False, 对于i>=k有f(i)=True |
相反的,我们可以用lower_bound来实现upper_bound
1 | // f满足存在一个k值得对于i>=k有f(i)=False, 对于i<k有f(i)=True |
实际使用时写在模板里做了一些改进写成了下面的样子,把b、e的类型写成ll可以避免传参是一个是int一个是unsigned int或者一个ll的情况会编译报错,f的类型写成F而没有用function也是避免要写强制类型转换,使用时可以直接传lambda表达式。
1 | template<typename F> |