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

//return index location of key if it
//is with range from start to end inclusive.
//return -1 if it is not within that range.
//Run time: let n = end-start+1
//Best case: O(1)
//Worst case: O(n)
int linearSearch(string A[], int start, int end, string key)
{
	for (int i = start; i <= end; i++)
	{
		if (key == A[i])
			return i;
	}

	return -1;
}

//Assume given array A is SORTED!!!!
//return index of key within given range,
//return -1 if key not in given range
//Let n = end-start+1 (total number of items to search)
//Run time: O(log n) (worst-case!)
//What!?!? the Choppng Number of n?!?
//That is unbelievably fast!!!!!!!
int binarySearch(string A[], int start, int end, string key)
{
	int s = start;
	int e = end;

	while (s <= e)
	{
		int m = (s + e) / 2;

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

	return -1;
}

int main()
{
	string words[16];
	words[0] = "alpaca";
	words[1] = "bee";
	words[2] = "cat";
	words[3] = "dog";
	words[4] = "elephant";
	words[5] = "fox";
	words[6] = "gwar";
	words[7] = "horse";
	words[8] = "ilk";
	words[9] = "juraf";
	words[10] = "kangaroo";
	words[11] = "llama";
	words[12] = "monkey";
	words[13] = "norbert";
	words[14] = "ostrich";
	words[15] = "possum";

	//Implement a basic search function: (Quiz)
	/*
	cout << linearSearch(words, 0, 15, "llama") << endl; //11
	cout << linearSearch(words, 0, 15, "gwar") << endl; //6
	cout << linearSearch(words, 4, 12, "ilk") << endl; //8
	cout << linearSearch(words, 3, 8, "llama") << endl; //-1
	cout << linearSearch(words, 0, 15, "leech") << endl; //-1
	*/

	//Assume the array is sorted, design a faster way to search
	cout << binarySearch(words, 0, 15, "llama") << endl; //11
	cout << binarySearch(words, 0, 15, "gwar") << endl; //6
	cout << binarySearch(words, 4, 12, "ilk") << endl; //8
	cout << binarySearch(words, 3, 8, "llama") << endl; //-1
	cout << binarySearch(words, 0, 15, "leech") << endl; //-1

	return 0;
}