526互联

C++STL库 二分查找，以及对set集合进行二分查找，来源于”leetcode7022. 限制条件下元素之间的最小绝对差“

发布时间 2023-08-13 14:07:40作者: 深情的山鸡

C++的头文件<algorithm>中有用于二分查找的函数，lower_bound()、upper_bound()以及binary_search()：

lower_bound()：返回大于等于目标值的第一个位置
upper_bound()：返回大于目标值的第一个位置，
binary_search()：若目标值存在则返回true，否则返回false

参数列表：（起始位置，结束位置，目标值）

 

STL库中的容器同样实现了二分查找函数，比如set、map有序容器均实现了上述lower_bound()、upper_bound()

在实际应用中容器的成员函数的查找效率比STL库中函数的查找效率高了几个数量级

例如在下面这个例子中，十万数据规模，分别调用STL库中的lower_bound()函数和set集合中的成员函数lower_bound()进行一万次二分查询，前者用时11s多，而后者只需要几毫秒。

 

以上来自今天力扣第 358 场周赛当中的第三题7022. 限制条件下元素之间的最小绝对差，使用窗口遍历+二分可以很方便的解决该问题，这也是一道完美应用数据结构的一道题。使用注释那条语句则会卡在用例2008/2013处

代码如下：

    class Solution
    {
    public:
        int minAbsoluteDifference(vector<int> &nums, int x)
        {
            if (nums.size() == 1)
                return 0;
            int i = 0, j = x, ans = INT_MAX, n = nums.size();
            set<int> st;
            for (; j < n; i++, j++)
            {
                st.insert(nums[i]);
                // auto it = lower_bound(st.begin(),st.end(),nums[j]);
                auto it = st.lower_bound(nums[j]);
                if (it == st.end())
                {
                    it--;
                    ans = min(ans, abs(*it - nums[j]));
                }
                else if (it == st.begin())
                {
                    ans = min(ans, abs(*it - nums[j]));
                }
                else
                {
                    ans = min(ans, abs(*it - nums[j]));
                    it--;
                    ans = min(ans, abs(*it - nums[j]));
                }
            }
            return ans;
        }
    };