C++STL 二分函数源码剖析

下面是 lower_bound 和 upper_bound 的源码。

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

我们可以忽略掉相同的类模板，只关注不同的部分：

// upper_bound
_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;
	}
}
// lower_bound
_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;
}

首先是计算出区间长度的半(向下取整)，如果为零，则说明当前区间长度为1，则返回该值。

否则的话，找到区间中点位置即 __middle = __first + __len ，然后将该值与 __val 对比。

对于 upper_bound：

如果 __val < *__middle 则说明 __middle 及后面的元素均满足 >=__val，缩小右边界 __len = __half.

否则则说明 __middle 及前面的元素均满足 <__val，缩小左边界 __first = __middle;++__first;__len = __len - __half - 1;.

对于 lower_bound：

如果 *__middle < __val 则说明 __middle 及前面的元素均满足 <__val，缩小左边界 __first = __middle;++__first;__len = __len - __half - 1;.

否则则说明 __middle 及后面的元素均满足 >=__val，缩小右边界 __len = __half.

更一般的，对于 lower_bound，如果 __comp() 返回值是 true 则缩小左边界，否则缩小右边界，二分停止的位置为第一个 false 的位置，而 upper_bound 的操作相反。