Binary search for random access iterators in C++

Question

I wrote a generic binary search routine in C++ for ranges that are specified by random access iterators. In case the user inputs a range with non-random access iterators, an exception will be thrown. My code is below:

binary_search.h

#ifndef CODERODDE_BINARY_SEARCH_H
#define CODERODDE_BINARY_SEARCH_H

#include <iterator>

namespace coderodde {

    template<typename RandomIt, typename T>
    RandomIt search(RandomIt begin,
                    RandomIt end,
                    T value,
                    std::random_access_iterator_tag)
    {
        RandomIt save_end = end;

        while (begin != end)
        {
            RandomIt middle = begin + ((end - begin) >> 1);

            if (value < *middle)
            {
                end = middle;
            }
            else if (value > *middle)
            {
                begin = middle + 1;
            }
            else
            {
                return middle;
            }
        }

        return save_end;
    }

    template<typename NonRandomIt, typename T>
    NonRandomIt search(NonRandomIt begin,
                       NonRandomIt end,
                       T value,
                       std::input_iterator_tag)
    {
        throw std::runtime_error(
                   "coderodde::search requires random access iterators.");
    }

    template<typename It, typename T>
    It search(It begin, It end, T value)
    {
        return search(begin, end, value, typename std::iterator_traits<It>::iterator_category());
    }
}

#endif /* CODERODDE_BINARY_SEARCH_H */

And the demonstration code is:

#include <iostream>
#include <iterator>
#include <list>
#include <stdexcept>
#include <vector>
#include "binary_search.h"

using coderodde::search;
using std::boolalpha;
using std::cerr;
using std::cout;
using std::end;
using std::endl;
using std::list;
using std::runtime_error;
using std::vector;

int main() {
    cout << "int array:" << endl;
    int arr[] = { 1, 3, 4, 4, 5, 7, 10, 15, 23 };
    size_t length = sizeof(arr) / sizeof(arr[0]);
    int* p = search(arr, arr + length, 1);
    cout << "The 1st iterator points to: " << *p << endl;
    p = search(arr, arr + length, 7);
    cout << "The 2nd iterator points to: " << *p << endl;
    p = search(arr, arr + length, 23);
    cout << "The 3rd iterator points to: " << *p << endl;

    p = search(arr, arr + length, 8);

    cout << "8 not found: " << boolalpha << (p == end(arr)) << endl;

    cout << "int vector:" << endl;
    vector<int> vec = { 1, 3, 4, 4, 5, 7, 10, 15, 23 };
    vector<int>::iterator it = search(vec.begin(), vec.end(), 1);
    cout << "The 1st iterator points to: " << *it << endl;
    it = search(vec.begin(), vec.end(), 7);
    cout << "The 2nd iterator points to: " << *it << endl;
    it = search(vec.begin(), vec.end(), 23);
    cout << "The 3rd iterator points to: " << *it << endl;

    p = search(arr, arr + length, 8);

    cout << "8 not found: " << boolalpha << (p == end(arr)) << endl;

    try {
        list<int> lst = { 1, 3, 4, 4, 5, 7, 10, 15, 23 };
        search(lst.begin(), lst.end(), 4);
    } catch (runtime_error& err) {
        cerr << err.what() << endl;
    }
}

The output is:

int array:
The 1st iterator points to: 1
The 2nd iterator points to: 7
The 3rd iterator points to: 23
8 not found: true
int vector:
The 1st iterator points to: 1
The 2nd iterator points to: 7
The 3rd iterator points to: 23
8 not found: true
coderodde::search requires random access iterators.

As always, any critique is much appreciated.

Answer 1

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<typename RandomIt, typename T>
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<typename RandomIt, typename Cat = typename std::iterator_traits<RandomIt>::iterator_category>
RandomIt search(RandomIt begin,
                RandomIt end,
                typename std::iterator_traits<RandomIt>::value_type const& 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<typename RandomIt, typename Cat = typename std::iterator_traits<RandomIt>::iterator_category>
RandomIt search(RandomIt begin,
                RandomIt end,
                typename std::iterator_traits<RandomIt>::value_type const& value);

// Partial specialization for Random Iterator
template<typename RandomIt>
RandomIt search<RandomIt, std::random_access_iterator_tag>(
                RandomIt begin,
                RandomIt end,
                typename std::iterator_traits<RandomIt>::value_type const& 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<> but I leave that as an exercise.

Make Intenet clear

        RandomIt middle = begin + ((end - begin) >> 1);

Not everybody will see >> 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);