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

#define MAX 10

using namespace std;

struct student {
	int num;
};

bool operator<(student st1, student st2)
{
	return (st1.num < st2.num) ? true : false;
}

bool operator==(student st1, student st2)
{
	return (st1.num == st2.num) ? true : false;
}

// a could be array or vector -- needs op[] defined
template <typename T1, typename T2>
void bin_search(T1 a, int left, int right, T2 x)
{
	if (right < left) {
		cout << "element not found" << endl;
		return;
	}

	int mid = (right + left) / 2;

	if (a[mid] == x) {
		cout << "element found" << endl;
	} else if (a[mid] < x) {
		bin_search(a, mid + 1, right, x);
	} else {
		bin_search(a, left, mid - 1, x);
	}
}

int main()
{
	student arr_st[MAX];
	vector<student> vec_st;

	for (int i = 0; i < MAX; i++) {
		student stk;
		stk.num = 1 + (rand() % 100);

		arr_st[i] = stk;
		vec_st.push_back(stk);
	}

	sort(arr_st, arr_st + MAX);
	sort(vec_st.begin(), vec_st.end());

	cout << "(array)  Sorted elements are: ";
	for (int i = 0; i < MAX; i++) {
		cout << " " << arr_st[i].num;
	}
	cout << endl;

	cout << "(vector) Sorted elements are: ";
	for (int i = 0; i < MAX; i++) {
		cout << " " << vec_st[i].num;
	}
	cout << endl;

	student stk;
	stk.num = 1;
	while (stk.num) {
		cout << "Enter element to serched (0 to end): ";
		cin >> stk.num;

		if (stk.num) {
			cout << "bin_search(array) : ";
			bin_search(arr_st, 0, MAX - 1, stk);
			cout << "bin_search(vector): ";
			bin_search(vec_st, 0, MAX - 1, stk);
		}
	}

	return 0;
}