刷题用STL学习之二分查找

这几天一边刷着leetcode的每日一题，一边翻着微软的C++文档，来记录一下做题中用到的，新学的函数。

这篇文章主要讲二分查找相关的三个函数binary_search、upper_bound、lower_bound。

什么是二分查找

二分查找也叫折半查找，在排序好的数组里面，每次与区间中间的元素进行比较，如果大了就在右边区间继续进行二分查找，如果小了就在左边元素进行查找，时间复杂度是$O(\log n)$。

注意：算法库中的二分查找相关的函数默认传入的范围按照从小到大的顺序排好序了，如果是从大到小，可以将二元谓词设置为大于。

binary_search

binary_search是算法库里面的二分查找函数，查找范围内是否存在与指定值相等的元素，最多接受4个参数：

迭代器，标志区间开始位置（闭）
迭代器，标志区间结束位置（开）
要查找的值
（可选）二元谓词，规定一个元素小于另一个元素的条件

这个函数作用不大，它只返回有还是没有，也不能返回元素的位置，几乎没有用过，但是下面两个函数就很有用。

upper_bound

upper_bound光看名字不好理解，作用是通过二分查找，返回范围中第一个大于指定值的元素的迭代器，如果不存在则返回区间结束位置，参数同上：

迭代器，标志区间开始位置（闭）
迭代器，标志区间结束位置（开）
要查找的值
（可选）二元谓词，规定一个元素小于另一个元素的条件

lower_bound

lower_bound光看名字是不是觉得它作用跟upper_bound的作用相反，返回范围中第一个小于指定值的元素的迭代器，很反直觉的是，它的作用是返回范围中第一个大于等于指定值的元素的迭代器，参数同上，就不多重复了。

总结

如果只要知道是否存在元素就用binary_search，如果要大于指定值的元素的迭代器就选择两个bound，如果要包含指定值的就用lower_bound，不包含指定值的就用upper_bound。

实战

下面是一个leetcode每日一题：3111. 覆盖所有点的最少矩形数目

首先题目描述有点误导性，

每个矩形的左下角在某个点$(x_1, 0)$处，且右上角在某个点$(x_2, y_2)$处，其中$x_1 <= x_2$且$y_2 >= 0$，同时对于每个矩形都必须满足$x_2 - x_1 <= w$。

上面题目描述中说的$(x_2, y_2)$不一定要是points中的点，换个角度说，它限制我们的只有单个矩形的宽度不能大于$w$，高度我们直接假设都是最大，可以直接忽略y

忽略$y$之后，我们根据贪心还是什么的思想，我们先将每个点的$x$坐标按照从小到大的顺序排序好。假设每一个矩形都是最大宽度$w$，我们就从第一个$x$开始，第一个矩形覆盖了$[x_0,x_0+w]$的点，然后我们的下一个矩形就从第一个大于$x_0+w$的位置开始，每次矩形覆盖之后就跳到下一个没有覆盖的位置开始覆盖，直到所有点都被覆盖，代码如下：

class Solution {
public:
    int minRectanglesToCoverPoints(vector<vector<int>>& points, int w) {
        int n=0;
        vector<int>V(points.size());
        for(int i=0;i!=points.size();++i){
            V[i]=points[i][0];
        }
        sort(V.begin(),V.end());
        auto it=V.begin();
        while(it!=V.end()){
            it=upper_bound(it,V.end(),*it+w);
            ++n;
        }
        return n;
    }
};

在上面代码中我们就用upper_bound跳到下一个没有被覆盖的位置，即第一个大于*it+w的位置。

通过截图：

实测会比朴素方法还慢，估计是常数太大了，在数据太少的情况下不如朴素方法。