#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

static const int NOT_FOUND = -1;
/**
 * Performs the standard binary search using two comparisons
 * per level. This is a driver that calls the recursive method.
 */
template <class Comparable>
int binarySearch( const vector<Comparable> & a,
                  const Comparable & x )
{
    return binarySearch( a, x, 0, a.size( ) - 1 );
}

/**
 * Recursive routine.
 */
template <class Comparable>
int binarySearch( const vector<Comparable> & a,
                  const Comparable & x, int low, int high )
{
    if( low > high )
        return NOT_FOUND;

    int mid = ( low + high ) / 2;

    if( a[ mid ] < x )
        return binarySearch( a, x, mid + 1, high );
    else if( x < a[ mid ] )
        return binarySearch( a, x, low, mid - 1 );
    else
        return mid;
}

/*
 * Main program tests both this binary search routine and the
 * lower_bound routine a-la STL.
 */
int main( )
{
    const int SIZE = 8;
    vector<int> a( SIZE );

    for( int i = 0; i < SIZE; i++ )
        a[ i ] = i * 2;

    for( int j = 0; j < SIZE * 2; j++ )
        cout << "Found " << j << " at " << binarySearch( a, j ) << endl;

    for( int k = 0; k < SIZE * 2; k++ )
    {
        int *result = lower_bound( a.begin( ), a.end( ), k );
        cout << k << ": ";
        if( result == &a[ 0 ] + SIZE )
            cout << "EM";
        else
            cout << *result;
        cout << endl;
    }
            
    return 0;
}