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

algorithm, binary-search, c++, stl

Solution

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

Problem

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?!) 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 ``` 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`.

Original source