C++ 标准库里的 std::lower_bound 和 std::upper_bound 二分搜索

作者: , 共 3163 字 , 共阅读 0

C++对一个有序序列[first, last)firstlast都是iterator,可简单理解为位置指针),以及指定值v,标准库直接提供二分查找的函数std::lower_boundstd::upper_bould

auto begin = std::lower_bound(first, last, v);
auto end = std::upper_bound(first, last, v);

此时[begin, end)是所有满足刚好等于v的位置范围,且begin之前的值都小于vend(含)之后的数都大于v。这个范围也有一个函数直接返回:std::tie(begin, end) = std::equal_range(first, last, v)

下面是g++( libstdc++)里的实现,可以学习一下标准二分查找的写法:

template<typename _ForwardIterator, typename _Tp, typename _Compare> 
_ForwardIterator __lower_bound(_ForwardIterator __first, _ForwardIterator __last, 
    const _Tp& __val, _Compare __comp)
{
    typedef typename iterator_traits<_ForwardIterator>::difference_type _DistanceType;
    _DistanceType __len = std::distance(__first, __last);

    while (__len > 0) {
        _DistanceType __half = __len >> 1;
        _ForwardIterator __middle = __first;
        std::advance(__middle, __half);
        if (__comp(__middle, __val)) {
            __first = __middle;
            ++__first;
            __len = __len - __half - 1;
        }
        else __len = __half;
    }

    return __first;
}

template<typename _ForwardIterator, typename _Tp, typename _Compare>
_ForwardIterator __upper_bound(_ForwardIterator __first, _ForwardIterator __last, 
    const _Tp& __val, _Compare __comp)
{
    typedef typename iterator_traits<_ForwardIterator>::difference_type _DistanceType;
    _DistanceType __len = std::distance(__first, __last);

    while (__len > 0) {
        _DistanceType __half = __len >> 1;
        _ForwardIterator __middle = __first;
        std::advance(__middle, __half);
        if (__comp(__val, __middle)) __len = __half;
        else {
            __first = __middle;
            ++__first;
            __len = __len - __half - 1;
        }
    }

    return __first;
}

// _CompareItTp 和 _CompareTpIt 都是小于运算符,只是一个判断 *it < v,后一个判断 v < *it。
template<typename _ForwardIterator, typename _Tp, typename _CompareItTp, typename _CompareTpIt>
pair<_ForwardIterator, _ForwardIterator>__equal_range(_ForwardIterator __first, _ForwardIterator __last, 
    const _Tp& __val, _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
{
    typedef typename iterator_traits<_ForwardIterator>::difference_type _DistanceType;
    _DistanceType __len = std::distance(__first, __last);

    while (__len > 0)
    {
        _DistanceType __half = __len >> 1;
        _ForwardIterator __middle = __first;
        std::advance(__middle, __half);

        if (__comp_it_val(__middle, __val)) {
            __first = __middle;
            ++__first;
            __len = __len - __half - 1;
        }
        else if (__comp_val_it(__val, __middle)) __len = __half;
        else {
            _ForwardIterator __left = std::__lower_bound(__first, __middle, __val, __comp_it_val);
            std::advance(__first, __len);
            _ForwardIterator __right = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
            return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
        }
    }

    return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
}

Q. E. D.

类似文章:
编程 » C++, 智能指针
前面已经提到std::shared_ptr有三个缺陷:
编程 » C++, 智能指针
理论上而言,当 C++提供了std::unique_ptr, C++的程序就不应该出现普通指针了。所有普通指针都可以用std::unique_ptr代替,避免手动删除对象。
智能指针在现代 C++里用得越多。以前只知道它大致的原理,比如使用引用计数。但很多实现细节并不清楚,最直接的,它是如何实现多线程安全的?今天找了 gnu c++ library 的实现好好看了一下。
编程 » C++, 异步
C++11 的标准异步库至少包含下面内容:
std::thread是 C++ 11 新引入的标准线程库。在同样是 C++ 11 新引入的 lambda 函数的辅助下,std::thread用起来特别方便:
编程 » C++, C++标准库
std::tuple的原理并不复杂,但有些细节非常有意思。其中有一个是至少在gnu C++ std的实现中,std::tuple是倒序存储的:
编程 » C++, 数据容器, folly
folly::dynamic提供类似于C++的动态类型。和std::any可以容纳任意类型不一样,folly::dynamic只支持保存以下几种类型:
数学 » mosek
线性或二次优化经常会碰到无解情况。一个典型的线性或二次优化问题如下:
看到网上有片段,提到没有必要自己实现自旋锁,因为标准库的 std::mutex 和现在的自旋锁的实现没有两样。比较好奇,翻了一些资料,试图找到答案。
编程 » Python
今天写一段程序时遇到一个问题,查了好一会才搞清楚。代码可以简化为下面这个小代码:
周末约了人一起去中门寺挖水晶。开车直接导航到「中门寺生态园」,但这里在修路被堵,直接扫码进旁边的小区,进去之后立即左拐有一条土路,沿着土路一直往前开就到了,终点处有一大片平地可停车,也可以继续往前开停在路边。后面这一段不能用导航,导航里没有这条土路会让绕一个巨大的圈。
跟着绿野的队伍走了一次百花山到黄安坨的穿越,全程 14 公里,爬升将近 1000 米。轨迹可从参考百花山-黄安坨(实际爬升比这个要大一些,因为我们上了主峰白球雷达站,然后起始位置也要更偏下一点)。