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

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

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.

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