Menu
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
eof[first,last)are partitioned with respect to the expressionse < valueand!(value < e)orcomp(e, value)and!comp(value, e). Also, for all elementseof[first,last),e < valueimplies!(value < e)orcomp(e, value)implies !comp(value, e).Returns:
trueif there is an iteratoriin the range[first,last)that satisfies the corresponding conditions:!(*i < value) && !(value < *i)orcomp(*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.
251
1. binary_search(start_ptr, end_ptr, num) : This function returns boolean true if the element is present in the container, else returns false.
C++ bsearch()The bsearch() function in C++ performs a binary search of an element in an array of elements and returns a pointer to the element if found. The bsearch() function requires all elements less than the element to be searched to the left of it in the array.
The algorithm to use is std::binary_search , that directly returns a bool representing whether the searched value has equivalent elements in the collection.
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.
According to draft N4431, the function std::binary_search in the algorithms library returns a bool, [binary.search]:
Binary Search functions in C++ STL (binary_search, lower_bound and upper_bound) Binary search is an important component in competitive programming or any algorithmic competition, having knowledge of shorthand functions reduces the time to code them. This searching only works when container is sorted.
For std::binary_search to succeed, the range [first, last) must be at least partially ordered with respect to value, i.e. it must satisfy all of the following requirements: A fully-sorted range meets these criteria. The first version uses operator< to compare the elements, the second version uses the given comparison function comp .
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
184
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
