c++ - 为什么std::binary_search使用ForwardIterator，而不使用RandomIterator？

我很惊讶它在使用不支持middle的ForwardIterator时如何计算auto middle = first + (last - first) / 2;。

最佳答案

std::binary_search()的行为在概念上等效于(对于非比较器版本)

template <class ForwardIterator, class T>
  bool binary_search (ForwardIterator first, ForwardIterator last, const T& val)
{
  first = std::lower_bound(first,last,val);
  return (first!=last && !(val<*first));
}

其中std::lower_bound()可根据需要专门用于不同的迭代器(例如，将std::distance()和std::advance()用于ForwardIterator，以及将其他技术用于不同的迭代器(如果适用于实现))。请记住，Bidirectional和RandomAccess迭代器是ForwardIterator的特化。