Robert Gould Robert Gould - 4 months ago 10
C++ Question

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

I need a binary search algorithm that is compatible with the C++ STL containers, something like

std::binary_search
in the standard library's
<algorithm>
header, but 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 of the fact that my data is sorted to get the benefits of a binary search, not a linear search.

so far
lower_bound
and
upper_bound
fail 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. Like, say,
boost::binary_search
.

Answer

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 && !(val < *i))
        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).