C++标准库里的二分查找算法剖析
原创
作为后台开发团队，服务性能优化是我们持续在做的事情，涵盖面比较广，包括锁优化、缓存优化、查找优化等等。这里举一个查找优化方面的例子进行说明。
业务场景是查找网络拓扑中的边并进行权重的更新。概况而言就是在容器（比如vector）中查找对应元素，有则执行更新操作。原有的实现采用find_if。用法参考这里，比较直观，只需定义一个==比较函数即可，类似：
auto it = std::find_if(std::begin(v), std::end(v), [&i](uint32_t e) -> bool {
return e == i;
});find_if的问题在于它是线性复杂度的，这是它在gcc-9.1.0中的实现：
/// This is an overload used by find algos for the Input Iterator case.
template<typename _InputIterator, typename _Predicate>
inline _InputIterator __find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred, input_iterator_tag)
{
while (__first != __last && !__pred(__first)) ++__first;
return __first;
} 出于其他考虑，我们保留了vector容器，再引入二分查找算法，正好C++标准库提供了lower_bound，看起来符合我们的需求：
auto first = std::lower_bound(v.begin(), v.end(), i);
if(!(first == v.end()) && !(i < *first)){
std::cout << "item found!" << std::endl;
}由于lower_bound返回的是[v.begin(), v.end()]中第一个大于或等于查找值的迭代器，所以我们需要额外判断元素是否找到且真的相等。
简单比对find_if和lower_bound在不同大小（100~1000000）vector（元素已排序）下查找相同元素（最大元素）的耗时如下：
说明标准库还是值得信赖的，我们看下lower_bound在gcc-9.1.0的具体实现：
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;
}可以看到lower_bound就是个二分查找，其中涉及到两个函数，distance用于计算迭代器__first和__last的距离，进而在每次迭代的步长__half；advance用于向前推进步长：
template<typename _InputIterator>
inline _GLIBCXX14_CONSTEXPR typename iterator_traits<_InputIterator>::difference_type __distance(_InputIterator __first, _InputIterator __last, input_iterator_tag)
{
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
typename iterator_traits<_InputIterator>::difference_type __n = 0;
while (__first != __last)
{
++__first;
++__n;
}
return __n;
}
template<typename _RandomAccessIterator>
inline _GLIBCXX14_CONSTEXPR typename iterator_traits<_RandomAccessIterator>::difference_type __distance(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)
{
// concept requirements
__glibcxx_function_requires(_RandomAccessIteratorConcept<_RandomAccessIterator>)
return __last - __first;
}
template<typename _InputIterator, typename _Distance>
inline _GLIBCXX14_CONSTEXPR void __advance(_InputIterator& __i, _Distance __n, input_iterator_tag)
{
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
__glibcxx_assert(__n >= 0);
while (__n--) ++__i;
}
template<typename _BidirectionalIterator, typename _Distance>
inline _GLIBCXX14_CONSTEXPR void __advance(_BidirectionalIterator& __i, _Distance __n, bidirectional_iterator_tag)
{
// concept requirements
__glibcxx_function_requires(_BidirectionalIteratorConcept<_BidirectionalIterator>)
if (__n > 0)
while (__n--)
++__i;
else
while (__n++)
--__i;
}
template<typename _RandomAccessIterator, typename _Distance>
inline _GLIBCXX14_CONSTEXPR void __advance(_RandomAccessIterator& __i, _Distance __n, random_access_iterator_tag)
{
// concept requirements
__glibcxx_function_requires(_RandomAccessIteratorConcept<_RandomAccessIterator>)
if (__builtin_constant_p(__n) && __n == 1)
++__i;
else if (__builtin_constant_p(__n) && __n == -1)
--__i;
else
__i += __n;
}可以看到，对于RandomAccessIterator类型的__first和__last，distance可以在常数时间计算出距离（__last - __first），advance可以在常数时间推进指定步长（__i += __n），可是对于更一般的InputIterator，会退化到线性迭代，复杂度为O(n)。
下面以list和vector为例，给出lower_bound的这种行为的直观展示：
所以，标准库虽好，可不要违反科学哦，相信也不会有人在链表上使用二分查找吧O(∩_∩)O
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。