#include<bits/stdc++.h>
using namespace std;

#define int_MAX 50000
#define LOOP_COUNT 1e6
#define Time high_resolution_clock::time_point

random_device rd;

struct _values{
	int len;
	long long ls_ns, bs_ns;

	_values(int a, long long b, long long c) : len(a), ls_ns(b), bs_ns(c){}

};

bool operator < (_values a, _values b){
	return a.len<b.len;
}

ostream& operator << (ostream& out, _values v){
	out << v.len  << ", " << v.ls_ns <<  ", " << v.bs_ns << endl;
	return out;
}

vector<_values> to_plot;

int array_generator(int *arr, int len)
{
	uniform_int_distribution<int> hell(0, int_MAX); // in [0, int_MAX) interval
	for(int i=0; i<len; ++i){
		arr[i] = hell(rd);
	}
	stable_sort(arr, arr+len);
	return (rd() % int_MAX);
}

int _linear_search(int *arr, int len, int val)
{
	int idx = -1;
	for(int i=0; i<len; ++i){
		if(*(arr+i) == val){
			idx = i;
			break;
		}
	}
}

int _binary_search(int *arr, int len, int val)
{
	int i=0, j=len-1;
	int m;
	while(i<j){
		m = (i+j)/2;
		if(val>arr[m])
			i = m+1;
		else
			j = m;
	}
}

void doing_the_search(int *arr, int len, int key){
	using namespace std::chrono;
	int pos_l, pos_b;
	Time t1 = high_resolution_clock::now();
	//To fetch the average time, each search was done a number of times
	for(int i=0; i<LOOP_COUNT; ++i)
		pos_l = _linear_search(arr, len, key);
	Time t2 = high_resolution_clock::now();
	for(int i=0; i<LOOP_COUNT; ++i)
		pos_b = _binary_search(arr, len, key);
	Time t3 = high_resolution_clock::now();
	long long l4=0, l5=0;
	auto n1 = duration_cast<nanoseconds>(t2 - t1);
	auto n2 = duration_cast<nanoseconds>(t3 - t2);
	l4 = n1.count(); l5 = n2.count();
	cout << n1.count() << " & " << n2.count() << endl;
	to_plot.push_back(_values(len, l4, l5));
}

int main()
{
	int len, lenn;
	cout << "No of inputs: ";
	cin >> lenn;
	while(lenn--){
		int* p;
		cin >> len;
		cout << "Assigned len: " << len << endl;
		p = new int[len];
		if(!p){
			cout << "Allocation error!!!";
			return 0;
		}
		int key = array_generator(p, len);
		cout << "Key: " << key << endl ;
		doing_the_search(p, len, key);
	}
	ofstream fout("new.csv");
	sort(to_plot.begin(), to_plot.end());
	for(auto f : to_plot){
		cout << f;
		fout << f;
		//cout << endl;
	}
	return 0;
}