Why does std :: binary_search return a bool?

Question

According to project N4431 , the std::binary_search in the algorithm library returns 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); 

Required: The elements e of [first,last) separated relative to the expressions e < value and !(value < e) or comp(e, value) and !comp(value, e) . In addition, 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 .

Difficulty: no more than log ₂ (last - first) + O (1) comparisons.

Does anyone know why this is so?

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

Answer 1

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

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

Answer 2

The binary search algorithm relies on a strict weak order. This means that elements must be separated according to operator < or according to a custom comparator that has the same guarantees. This means that for a given query there does not have to be only one element. So you need lower_bound , upper_bound and equal_range to extract iterators.

Answer 3

It crashed into several different functions in C ++, since for reasoning it is almost impossible to say why someone did something anyway. binary_search will tell you if such an element exists. If you need to know where they are, use lower_bound and upper_bound , which will give a start and end iterator, respectively. There is also equal_range , which gives you both a start and an end right away.

---

Since others seem to think that it is obvious why it was created this way, I will argue about why it is difficult / impossible to answer if you are not Alexander Stepanov or someone who worked with him.

Unfortunately, the SGI STL FAQ does not mention binary_search at all. This explains that list<>::size is linear time or pop returning void . It seems like they thought binary_search was special enough to document it.

Take a look at a possible performance improvement mentioned in @ user2899162:

You can find the original implementation of the SGI STL binary_search here . Looking at this, you can greatly simplify it (we all know how terrible the internal names in the standard library are):

 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 exact same performance. If they really wanted him to take advantage of possible performance improvements, they would not have implemented it in terms of a slower one, so it does not seem like they did it that way.

Now let's look at it just as a convenient function

This just a convenient feature seems more likely, but looking through the STL, you will find many other algorithms where this could be possible. Looking at the above implementation, you will see that it is just trivially more than std::find(begin, end, value) != end; but we have to write all the time and we don’t have a convenience function that returns a bool . Why is it here and not all other algorithms too? This is not very obvious and cannot be simply explained.

In conclusion, I find this far from obvious and I do not know if I can confidently and honestly answer it.

Answer 4

The standard library contains variants of the binary search algorithm that iterators return. They are called std :: lower_bound and std :: upper_bound . I think the rationale for std::binary_search return bool is that it is not clear which iterator should return in the case of equivalent elements, whereas in the case of std::lower_bound and std::upper_bound is understandable.

Perhaps there were performance considerations, because theoretically std::binary_search could be implemented to work better in the case of several 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.

Answer 5

If you want to get an iterator by value, you can use std :: equal_range , which will return 2 iterators, one at the bottom and one at the top of the range of values ​​equal to the one you are looking for.

Since the only requirement is that the values ​​are sorted and not unique, there is no simple "find" that would return the iterator to the single element you are looking for. If there is only one element equal to the value you are looking for, the difference between 1 iterators will be only 1.