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

//Rule: no loops

//Return index location of key within A from start to end inclusive
//Let n be number of items in range, (end-start+1).
//Run time: O(log n)
int binarySearch(double * A, int start, int end, double key)
{
	if (start > end ) //base case: no items in search range
	{
		return -1;
	}
	else //recursive case
	{
		int mid = (start + end) / 2;

		//check if mid item is eqaul, bigger, or smaller than key
		if(key == A[mid])
		{
			return mid;
		}
		else if(key < A[mid] )
		{
			return binarySearch(A, start, mid - 1, key);
		}
		else //key > A[mid]
		{
			return binarySearch(A, mid + 1, end, key);
		}
	}
}

int counter = 0;

//Print out move sequence to solve Hanoi:
//How to move top n discs from platform A to platform
//C, using platform B as a buffer.
void hanoi(int n, string A, string B, string C)
{
	if (n==0) //base case
	{
		//No discs, do nothing!
	}
	else //recursive case
	{
		//step 1: move top n-1 discs from A to B, using C as buffer
		hanoi(n - 1, A, C, B);

		//step 2: move top disc from A to B
		cout << "Move top disc from: " << A << " to " << C << endl;
		counter++;

		//step 3: 
		hanoi(n - 1, B, A, C);
	}
}

int main()
{
	//12 items
	double items[] = { -50, -2.3, 1.2, 3.14, 5, 7, 12.3, 84, 98.6, 125.6, 254.8, 400.8};

	cout << binarySearch(items, 0, 11, 7) << endl; //5
	cout << binarySearch(items, 0, 11, 1.2) << endl; //2
	cout << binarySearch(items, 0, 11, 400.8) << endl; //11
	cout << binarySearch(items, 0, 11, -2.3) << endl;  //1
	cout << binarySearch(items, 0, 11, 25) << endl;   //-1, since 25 is not there

	cout << "Hanoi game: " << endl;

	//Print out solution to size 3 hanoi problem
	hanoi(63, "A", "B", "C");
	cout << counter << endl;

	return 0;
}