Robert Gould - 1 year ago 74
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`
.

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
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).