Binary Search is a very useful algorithm whenever we are dealing with an already sorted group of elements. If we take a look at the C++ STL we find a function called std::binary_search that implements this algorithm but upon further research, we learn that it only tells us if the search value is present in the container, rather than returning an iterator of the value found. So how do we implement a generic binary search function that finds the location of the value that we want to search? A simple implementation based on traditional binary search would look something like this:

Implementation #1

template<typename Iter, typename Val, typename Comp = std::less<>>
Iter binary_search1(Iter begin, Iter end, const Val& search_val, Comp comp = {})
{
    auto original_end = end; //saving end to return when value is not found

    while (begin != end)
    {
        auto mid = begin + (end - begin) / 2;

        if (search_val == *mid) 
        {
            return mid;
        }
        else if (!comp(search_val, *mid)) //search_val > mid
        {
            begin = mid + 1;
        }
        else //search_val < mid
        {
            end = mid;
        }
    }

    return original_end;
} 

While the first implementation follows the common steps needed to perform binary search it, is not taking advantage of C++ library features that could help shorten and simplify the code. For that reason, the second implementation presented below makes use of std::lower_bound: a function from the algorithm header that returns an iterator to the first element that is greater than or equal to the search value, or an iterator to the end of the container if no value was found.

Implementation #2 (Using lower_bound)

template<typename Iter, typename Val, typename Comp = std::less<>>
Iter binary_search2(Iter begin, Iter end, const Val& search_val, Comp comp = {})
{
    auto found_itr = std::lower_bound(begin, end, search_val, comp);

    if (found_itr != end && !comp(search_val, *found_itr)) //search_val >= found_itr
    {
        return found_itr;
    }

    return end;
}

Clearly, the use of std::lower_bound makes the implementation of binary search a rather straightforward task as it takes away from most of the error-prone details that are present in the algorithm.

Conclusion

Since C++ doesn’t provide a proper binary search function that returns the iterator of the value to be found, it is needed to write additional code to provide a generic and useful solution. Luckily, the use of std::lower_bound eases the implementation of the algorithm and allows us to enjoy the benefits of working with a sorted container.

Source Code