为什么 std::binary_search return 布尔值？

Question

根据草案 N4431，算法库 return 中的函数 std::binary_search 是 bool，[binary.search]:

  template<class ForwardIterator, class T>
  bool binary_search(ForwardIterator first, ForwardIterator last,
                     const T& value);

  template<class ForwardIterator, class T, class Compare>
  bool binary_search(ForwardIterator first, ForwardIterator last,
                     const T& value, Compare comp);
Requires: The elements e of [first,last) are partitioned with respect to the expressions e < value and !(value < e) or comp(e, value) and !comp(value, e). Also, for all elements e of [first,last), e < value implies !(value < e) or comp(e, value) implies !comp(value, e).

Returns: true if there is an iterator i in the range [first,last) that satisfies the corresponding conditions: !(*i < value) && !(value < *i) or comp(*i, value) == false && comp(value, *i) == false.

Complexity: At most log₂(last - first) + O(1) comparisons.

有人知道为什么会这样吗？

大多数其他通用算法 return 元素的迭代器或等效于指示元素序列末尾的迭代器的迭代器（即，元素序列中要考虑的最后一个元素之后的一个迭代器）序列），这是我所期望的。

Answer 1

它在 C++ 中分为多个不同的函数，至于推理，几乎不可能说出为什么有人以这种或另一种方式制作某物。 binary_search will tell you if such an element exists. If you need to know the location of them use lower_bound and upper_bound which will give the begin/end iterator respectively. There's also equal_range 一次给你开始和结束。

由于其他人似乎认为以这种方式创建它的原因是显而易见的，所以如果您不是 Alexander Stepanov 或与他共事的人，我将论证我的观点为什么 hard/impossible 回答。

遗憾的是 SGI STL FAQ 根本没有提到 binary_search。它解释了 list<>::size 是线性时间或 pop 返回 void 的原因。他们似乎认为 binary_search 没有足够的特殊性来记录它。

让我们看看@user2899162提到的可能的性能提升：

您可以找到 SGI STL 算法的原始实现 binary_search here。看看它，几乎可以将它简化为（我们都知道标准库中的内部名称有多糟糕）：

template <class ForwardIter, class V>
bool binary_search(ForwardIter first, ForwardIter last, const V& value) {
    ForwardIter it = lower_bound(first, last, value);
    return it != last && !(value < *it);
}

如您所见，它是根据 lower_bound 实施的，并获得了完全相同的性能。如果他们真的想让它利用可能的性能改进，他们就不会用较慢的那个来实现它，所以这似乎不是他们那样做的原因。

现在让我们看看它只是一个方便的函数

它只是一个方便的函数似乎更有可能，但通过 STL 查看您会发现许多其他算法，这可能是可能的。看看上面的实现，你会发现它只是比 std::find(begin, end, value) != end; 多了一点点，但我们必须一直写它，而且没有 returns a [=23 的便利函数=].为什么就在这里而不是所有其他算法呢？这不是很明显，不能简单地解释。

总之，我发现它远非显而易见，我真的不知道我是否可以自信而诚实地回答它。

Answer 2

标准库包含 return 个迭代器的二进制搜索算法的变体。他们被称为std::lower_bound and std::upper_bound。我认为 std::binary_search returning bool 背后的基本原理是，在等效元素的情况下，return 的迭代器不清楚，而在 std::lower_bound 和 [ 的情况下=12=]很清楚

也可能有性能方面的考虑，因为理论上 std::binary_search 可以在多个等效元素和某些类型的情况下实现更好的性能。然而，至少一个标准库的流行实现（libstdc++）使用 std::lower_bound 实现了 std::binary_search，此外，它们具有相同的理论复杂性。

Answer 3

二分查找算法依赖于严格的弱排序。这意味着元素应该根据 operator < 或根据具有相同保证的自定义比较器进行分区。这意味着对于给定的查询不一定只能找到一个元素。因此，您需要 lower_bound、upper_bound 和 equal_range 函数来检索迭代器。

Answer 4

如果你想得到一个值的迭代器，你可以使用 std::equal_range 这将 return 2 个迭代器，一个在值范围的下限上，一个在上限上等于你要找的那个。

因为唯一的要求是值是排序的而不是唯一的，所以没有简单的 "find" 可以 return 您正在寻找的一个元素的迭代器。如果只有一个元素等于您要查找的值，则两个迭代器之间只会相差 1。

Answer 5

这个函数在1994版STL中的名称是isMember。我想你会同意具有该名称的函数应该 return bool

http://www.stepanovpapers.com/Stepanov-The_Standard_Template_Library-1994.pdf

Answer 6

这是一个 C++20 二进制搜索替代方案，returns 一个迭代器：

template<typename RandomIt, typename T, typename Pred>
inline
RandomIt xbinary_search( RandomIt begin, RandomIt end, T const &key, Pred pred )
    requires std::random_access_iterator<RandomIt>
    &&
    requires( Pred pred, typename std::iterator_traits<RandomIt>::value_type &elem, T const &key )
    {
        { pred( elem, key ) } -> std::convertible_to<std::strong_ordering>;
    }
{
    using namespace std;
    size_t lower = 0, upper = end - begin, mid;
    strong_ordering so;
    while( lower != upper )
    {
        mid = (lower + upper) / 2;
        so = pred( begin[mid], key );
        if( so == 0 )
        {
            assert(mid == 0 || pred( begin[mid - 1], key ) < 0);
            assert(begin + mid + 1 == end || pred( begin[mid + 1], key ) > 0);
            return begin + mid;
        }
        if( so > 0 )
            upper = mid;
        else
            lower = mid + 1;
    }
    return end;
}

只有在 begin 和 end 之间只有一个值与键匹配时，此代码才能正常工作。但是，如果您进行调试并且未定义 NDEBUG，代码将在您的调试器中停止。

为什么 std::binary_search return 布尔值？

Why does std::binary_search return bool?

c++

c++11

stl-algorithm