二分搜索/lower_bound/upper_bound

发表于 更新于 分类于 Valine： 本文字数： 2.3k 阅读时长 ≈ 2 分钟

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);});}