#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
template <class Iter>
void myInsertionSort(Iter begin, Iter end){
Iter p =begin;
p++;
if (p == end) return; 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;
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;
}