Binary search for random access iterators in C++
I wrote a generic binary search routine in C++ for ranges that are specified by random access iterators.

Very good idea.

In case the user inputs a range with non-random access iterators, an exception will be thrown. My code is below:

Bad idea. You are doing a runtime check for something that can be detected by the compiler. This should force a compile time error.
Code Review
template&lt;typename RandomIt, typename T&gt;
RandomIt search(RandomIt begin,
                RandomIt end,
                T value,
                std::random_access_iterator_tag)

No need for the type T here. In fact putting it here is probably a bad idea. As it allows you to search a vector of double with an integer. Now there is not much you can do with compiler standard conversions but at least you can make sure that the value passed to the function has already been converted to the correct type for comparison.
template&lt;typename RandomIt, typename Cat = typename std::iterator_traits&lt;RandomIt&gt;::iterator_category&gt;
RandomIt search(RandomIt begin,
                RandomIt end,
                typename std::iterator_traits&lt;RandomIt&gt;::value_type const&amp; value,
                std::random_access_iterator_tag)

Also I would not bother passing the fourth parameter that should be a type to the template. Then you can have a template specialization that implements it for random iterators only.
// Generic Declaration with no implementation.
template&lt;typename RandomIt, typename Cat = typename std::iterator_traits&lt;RandomIt&gt;::iterator_category&gt;
RandomIt search(RandomIt begin,
                RandomIt end,
                typename std::iterator_traits&lt;RandomIt&gt;::value_type const&amp; value);

// Partial specialization for Random Iterator
template&lt;typename RandomIt&gt;
RandomIt search&lt;RandomIt, std::random_access_iterator_tag&gt;(
                RandomIt begin,
                RandomIt end,
                typename std::iterator_traits&lt;RandomIt&gt;::value_type const&amp; value)
{
    // Your implementation here.
}

Now the code will generate a compile time error when you use anything but a random access iterator. With a tiny bit of effort you can do this in a single declaration using the new std::enable_if&lt;&gt; but I leave that as an exercise.
Make Intenet clear
        RandomIt middle = begin + ((end - begin) &gt;&gt; 1);

Not everybody will see &gt;&gt; 1 as a divide by 2. Don't do that it just makes the code unclear. Use the divide operator it express intent much better (and does not have any worse performance).
        RandomIt middle = begin + ((end - begin) / 2);