#include <stdio.h>
#include <vector>
using namespace std;

bool isInSortedList( vector<int> &v, int e, int l, int r ) {
    if (l > r)
        return false;
    else if (l == r)
        return v[l] == e;

    
    int m = (l+r)/2;

    if ( v[m] == e ) {
        return true;
    } else if (v[m] < e) {
        return isInSortedList( v, e, m+1, r );
    } else {
        return isInSortedList( v, e, l, m-1 );
    }
} 

vector<int> intersection( vector<int> &v1, vector<int> &v2 ) {
    vector<int> res;
    int v2size = v2.size();

    vector<int>::iterator it = v1.begin();

    while (it != v1.end() ) {
        if ( isInSortedList( v2, *it, 0, v2size -1 ) ) 
            res.push_back( *it );
        it++;
    }

    return res;
}


int main( void ) {
    vector<int> v;

    v.push_back( 1 );
    v.push_back( 3 );
    v.push_back( 5 );
    v.push_back( 6 );
    v.push_back( 9 );

    printf( "4 is not in the list: %d\n", isInSortedList( v, 4, 0, v.size() -1  ) );
    printf( "6 is in the list : %d\n", isInSortedList( v, 6, 0, v.size() -1  ) );
    printf( "9 is in the list : %d\n", isInSortedList( v, 9, 0, v.size() -1  ) );
    printf( "-6 is not in the list : %d\n", isInSortedList( v, -6, 0, v.size() -1  ) );
    printf( "10 is not in the list : %d\n", isInSortedList( v, 10, 0, v.size() -1  ) );
    
	
	vector<int> v2;
	v2.push_back( 1 );
	v2.push_back( 2 );
	v2.push_back( 4 );
	v2.push_back( 6 );
	v2.push_back( 9 );
	printf( "Intersection of {1,3,5,6,9} with {1,2,4,6,9} should be {1,6,9}\n" );
	vector<int> res = intersection( v, v2 );
	int i =0;
	for (i=0; i < res.size(); i++)
		printf( "%d ", res[i] );
	printf( "\n" );

    return 0;  
}