#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;


//Like figure 8.3, but using iterators.
//You cannot simply copy figure 8.3. It will not work because
// you cannot declare a tmp variable like they do (why? templates).
//However, you can get around this by using the standard library
// swap(x,y) function and changing the algorithm slightly.
//You can assume that the Iter is a random access iterator.
//  that is you can ++, --, add and substract ints to it.
template <class Iter>
void myInsertionSort(Iter begin, Iter end){
	Iter p =begin;
	p++;
	if (p == end) return; //only one element in list, no need to sort.
	for (;p != end; ++p) {
		Iter j;
		for (j=p; (j != begin) && (*j < *(j - 1)); --j)
			swap(*j,*(j - 1));
	}
}

bool myBinarySearchHelper(vector<int> & v, int start, int end, int e){
	if (start == end) 
		return (e == v[start]);
	int mid = (end+start)/2;
	if (e <= v[mid])
		return myBinarySearchHelper(v,start,mid,e);
	else 
		return myBinarySearchHelper(v,mid+1,end,e);
}

//
bool myBinarySearch(vector<int> & v, int e){
	return myBinarySearchHelper(v, 0 , v.size(), e);
}

void print(int e){
	cout << e << ' ';
}

int main() {
	vector<int> v;
	v.push_back(2); v.push_back(9); v.push_back(4); 
	v.push_back(5); v.push_back(7); v.push_back(3);
	v.push_back(8); v.push_back(1); v.push_back(10);
	
	for_each(v.begin(), v.end(), print);
	cout << endl;
	
	//You might want to replace this with sort() and implement the
	//myBinarySearch() first since its easier.
	myInsertionSort(v.begin(),v.end());
	for_each(v.begin(), v.end(), print);
	cout << endl;

	for (int i = 3; i< 12; i++){
		if (myBinarySearch(v, i))	
			cout << i << " is in " << endl;
		else
			cout << i << " is not in" << endl;
	}
	return 0;
	
}