CODEWITHSUNDEEP
c++c++11stl-algorithm
Stephen DeSalvo
Stephen DeSalvo

Reputation: 717

Why does std::binary_search return bool?

According to draft N4431, the function std::binary_search in the algorithms library returns a 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 log2(last - first) + O(1) comparisons.

Does anyone know why this is the case?

Most other generic algorithms either return an iterator to the element or an iterator that is equivalent to the iterator denoting the end of the sequence of elements (i.e., one after the last element to be considered in the sequence), which is what I would have expected.

Upvotes: 19

Views: 4628

Answers (6)

Bonita Montero
Bonita Montero

Reputation: 3101

Here's a C++20 binary-seach alternative that returns an iterator:

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

This code only works correctly if there's only one value between begin and end that matches the key. But if you debug and NDEBUG is not defined, the code stops in your debugger.

Upvotes: -1

Cubbi
Cubbi

Reputation: 47468

The name of this function in 1994 version of STL was isMember. I think you'd agree that a function with that name should return bool

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

Upvotes: 11

vitaut
vitaut

Reputation: 55675

The standard library contains variants of binary search algorithm that return iterators. They are called std::lower_bound and std::upper_bound. I think the rationale behind std::binary_search returning bool is that it wouldn't be clear what iterator to return in case of equivalent elements, while in case of std::lower_bound and std::upper_bound it is clear.

There might have been performance considerations as well, because in theory std::binary_search could be implemented to perform better in case of multiple equivalent elements and certain types. However, at least one popular implementation of the standard library (libstdc++) implements std::binary_search using std::lower_bound and, moreover, they have the same theoretical complexity.

Upvotes: 0

AliciaBytes
AliciaBytes

Reputation: 7439

It's split into multiple different functions in C++, as for the reasoning it's nearly impossible to tell why someone made something one way or another. 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 that gives you both the begin and end at once.

Since others seem to think that it's obvious why it was created that way I'll argue my points why it's hard/impossible to answer if you aren't Alexander Stepanov or someone who worked with him.

Sadly the SGI STL FAQ doesn't mention binary_search at all. It explains reasoning for list<>::size being linear time or pop returning void. It doesn't seem like they deemed binary_search special enough to document it.

Let's look at the possible performance improvement mentioned by @user2899162:

You can find the original implementation of the SGI STL algorithm binary_search here. Looking at it one can pretty much simplify it (we all know how awful the internal names in the standard library are) to:

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

As you can see it was implemented in terms of lower_bound and got the same exact performance. If they really wanted it to take advantage of possible performance improvements they wouldn't have implemented it in terms of the slower one, so it doesn't seem like that was the reason they did it that way.

Now let's look at it simply being a convenience function

It being simply a convenience function seems more likely, but looking through the STL you'll find numerous other algorithms where this could have been possible. Looking at the above implementation you'll see that it's only trivially more to do than a std::find(begin, end, value) != end; yet we have to write that all the time and don't have a convenience function that returns a bool. Why exactly here and not all the other algorithms too? It's not really obvious and can't simply be explained.

In conclusion I find it far from obvious and don't really know if I could confidently and honestly answer it.

Upvotes: 5

meneldal
meneldal

Reputation: 1747

If you want to get an iterator on a value, you can use std::equal_range which will return 2 iterators, one on the lower bound and one on the higher bound of the range of values that are equal to the one you're looking for.

Since the only requirement is that values are sorted and not unique, there's is no simple "find" that would return an iterator on the one element you're looking for. If there's only one element equal to the value you're looking for, there will only be a difference of 1 between the two iterators.

Upvotes: -1

Dalzhim
Dalzhim

Reputation: 2028

The binary search algorithm relies on strict weak ordering. Meaning that the elements are supposed to be partitioned according to the operator < or according to a custom comparator that has the same guarantees. This means that there isn't necessarily only one element that could be found for a given query. Thus you need the lower_bound, upper_bound and equal_range functions to retrieve iterators.

Upvotes: 3

Related Questions