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

作者: 张志强 , 2022-08-18 , 共 3163 字 , 共阅读 0

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

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

此时[begin, end)是所有满足刚好等于v的位置范围，且begin之前的值都小于v，end（含）之后的数都大于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);
}