Where can I get a "useful" C++ binary search algorithm?

Question

I need a binary search algorithm that is compatible with the C++ standard containers, something like std::binary_search in the standard library's <algorithm> header, but unlike std::binary_search, I need it to return the iterator that points at the result, not a simple boolean telling me if the element exists

(On a side note, what the hell was the standard committee thinking when they defined the API for binary_search!!!)

Edit: My main concern here is that I need the speed of a binary search, so although I can find the data with other algorithms, as mentioned below, I want to take advantage that my data is already sorted to get the benefits of a binary search, not just any search.

so far lower_bound and upper_bound fail, because if the datum is missing:

//lousy pseudo code
vector(1,2,3,4,6,7,8,9,0) //notice no 5
iter = lower_bound_or_upper_bound(start,end,5)
iter != 5 && iter !=end //not returning end as usual, instead it'll return 4 or 6

Also I really doubt lower_bound and upper_bound are implemented as binary_searches, because they work just as well with unsorted data, and there is no way to provide that information through arguments or policies. Ok as first mentioned by vividos, they DO require sorted data, which means they ARE binary searches, so the world is good again :)

Note: I'm also fine using an algorithm that doesn't belong to the std namespace as long as its compatible with containers. Likes say boost::binary_search or something

Answer 1

You should have a look at std::equal_range. It will return a pair of iterators to the range of all results.

Answer 2

There is a set of them:

http://www.sgi.com/tech/stl/table_of_contents.html

Search for:

• lower_bound
• upper_bound
• equal_range
• binary_search

On a separate note:

They were probably thinking that searching containers could term up more than one result. But on the odd occasion where you just need to test for existence an optimized version would also be nice.

Answer 3

std::lower_bound() :)

Answer 4

There is no such functions, but you can write a simple one using std::lower_bound, std::upper_bound or std::equal_range.

A simple implementation could be

template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val)
{
    // Finds the lower bound in at most log(last - first) + 1 comparisons
    Iter i = std::lower_bound(begin, end, val);

    if (i != end && *i == val)
        return i; // found
    else
        return end; // not found
}

Another solution would be to use a std::set, which guarantees the ordering of the elements and provides a method iterator find(T key) that returns an iterator to the given item. However, your requirements might not be compatible with the use of a set (for example if you need to store the same element multiple times).

Answer 5

Check this function, qBinaryFind:

RandomAccessIterator qBinaryFind ( RandomAccessIterator begin, RandomAccessIterator end, const T & value )

Performs a binary search of the range [begin, end) and returns the position of an occurrence of value. If there are no occurrences of value, returns end.

The items in the range [begin, end) must be sorted in ascending order; see qSort().

If there are many occurrences of the same value, any one of them could be returned. Use qLowerBound() or qUpperBound() if you need finer control.

Example:

QVector<int> vect;
 vect << 3 << 3 << 6 << 6 << 6 << 8;

 QVector<int>::iterator i =
         qBinaryFind(vect.begin(), vect.end(), 6);
 // i == vect.begin() + 2 (or 3 or 4)

The function is included in the <QtAlgorithms> header which is a part of the Qt library.