#include <iostream>
#include <string>
#include <vector>
#include <chrono>
using namespace std;

//return index location of key in given range from start to end.
//return -1 if key is not present in that range.
//Run time: Let n = end - start + 1
//run time: O(n)
int linearSearch(vector<double> &A, int start, int end, double key)
{//O(1) + n*O(1) + O(1) = O(n)
	for (int i = start; i <= end; i++) //n loops
	{ //cost of loop body: O(1)
		if (key == A[i])
			return i;
	}
	return -1; //O(1)
}

int binarySearch(vector<double>& A, int start, int end, double key)
{//O(1)

	//O(1)
	int s = start;
	int e = end;

	//#loops*O(1) = log_2 n * O(1) = O(log n)
	while (s <= e) //number loops: log_2 n
	{//total cost of body of loop: O(1)
		int m = (s + e) / 2;

		if (key == A[m])
			return m;
		else if (key < A[m])
			e = m - 1;
		else //key > A[m]
			s = m + 1;
	}

	//O(1)
	return -1;
}

int recBinSearch(vector<double>& A, int start, int end, double key)
{
	if (start > end) //base case
		return -1; //no items, can't be there
	else //recursive case
	{
		int m = (start + end) / 2;

		if (key == A[m])
			return m;
		if (key < A[m])
			return recBinSearch(A, start, m - 1, key);
		else //key > A[m]
			return recBinSearch(A,m + 1, end, key);
	}
}

int main()
{
	vector<double> X;
	X.push_back(-43.7);	//0
	X.push_back(-14);	//1
	X.push_back(-2.3);	//2
	X.push_back(1.3);	//3
	X.push_back(7);		//4
	X.push_back(13.2);	//5
	X.push_back(24);	//6
	X.push_back(37);	//7
	X.push_back(41);	//8
	X.push_back(52);	//9
	X.push_back(63.2);	//10
	X.push_back(71);	//11
	X.push_back(73);	//12
	X.push_back(89.4);	//13
	X.push_back(101);	//14
	X.push_back(125);	//15
	X.push_back(273);	//16
	X.push_back(289);	//17
	X.push_back(342);	//18
	X.push_back(404);	//19

	//Warmup: write a simple linear search function
	cout << linearSearch(X, 0, 19, 89.4) << endl;	//13
	cout << linearSearch(X, 0, 19, 404) << endl;	//19
	cout << linearSearch(X, 0, 19, -2.3) << endl;	//2
	cout << linearSearch(X, 0, 19, 45) << endl;	//-1
	cout << endl;
	
	//Binary Search:
	cout << binarySearch(X, 0, 19, 89.4) << endl;	//13
	cout << binarySearch(X, 0, 19, 404) << endl;	//19
	cout << binarySearch(X, 0, 19, -2.3) << endl;	//2
	cout << binarySearch(X, 0, 19, 45) << endl;	//-1
	cout << endl;

	//Binary Search:
	cout << recBinSearch(X, 0, 19, 89.4) << endl;	//13
	cout << recBinSearch(X, 0, 19, 404) << endl;	//19
	cout << recBinSearch(X, 0, 19, -2.3) << endl;	//2
	cout << recBinSearch(X, 0, 19, 45) << endl;	//-1
	cout << endl;
	return 0;
}