二分搜索/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
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
28
29
30
31
// 返回[b,e) 区间上首个大于等于x的元素的迭代器
template<typename Iter, typename VT>
Iter my_lower_bound(Iter b, Iter e, const VT& x)
{
if(!(*b<x)) return b;
if(*(e-1)<x) return e;
while(b<e-2){
Iter mid=b+(e-b)/2;
if(*mid<x)
b=mid;
else
e=mid+1;
}
return e-1;
}

// 返回[b,e) 区间上首个大于x的元素的迭代器
template<typename Iter, typename VT>
Iter my_upper_bound(Iter b, Iter e, const VT& x)
{
if(x<*b) return b;
if(!(x<*(e-1))) return e;
while(b<e-2){
Iter mid=b+(e-b)/2;
if(!(x<*mid))
b=mid;
else
e=mid+1;
}
return e-1;
}

二分算法看上去简单,如果不注意是很容易出错的,我觉得主要要注意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
2
3
4
5
6
7
8
9
10
11
12
// f满足存在一个k值得对于i<k有f(i)=False, 对于i>=k有f(i)=True
// 返回上述的k
template<typename I>
int lower_bound(I b, I e, function<bool(I)> f) {
if(b >= e) return e;
while(b < e - 1) {
auto m = b + (e-1-b) / 2;
if(!f(m)) b = m + 1;
else e = m + 1;
}
return f(b) ? b : e;
}

相反的,我们可以用lower_bound来实现upper_bound

1
2
3
4
5
6
7
8
// f满足存在一个k值得对于i>=k有f(i)=False, 对于i<k有f(i)=True
// 返回上述的k
template<typename I>
int upper_bound(I b, I e, function<bool(I)> f) {
return lower_bound(b, e, (function<bool(I)>)[&](I i){
return !f(i);
});
}

实际使用时写在模板里做了一些改进写成了下面的样子,把b、e的类型写成ll可以避免传参是一个是int一个是unsigned int或者一个ll的情况会编译报错,f的类型写成F而没有用function也是避免要写强制类型转换,使用时可以直接传lambda表达式。

1
2
3
4
template<typename F>
ll lb(ll b, ll e, F f) {if(b>=e) return e; while(b<e-1) {auto m=b+(e-1-b)/2; if(!f(m)) b=m+1; else e=m+1;} return f(b)?b:e;}
template<typename F>
ll ub(ll b, ll e, F f) {return lb(b, e, [&](ll i){return !f(i);});}