#include <vector>
#include <iostream>

int linearSearch(std::vector<int> &vectorToSearch, int itemToTest);
void bubbleSort(std::vector<int> &vectorToSort);
int binarySearch(std::vector<int> &vectorToSearch, int numToTest);

int main() {
	std::vector<int> myVector;
	myVector.push_back(5);
	myVector.push_back(20);
	myVector.push_back(18);
	myVector.push_back(3);
	myVector.push_back(9);
	myVector.push_back(4);
	myVector.push_back(11);
	myVector.push_back(30);
	myVector.push_back(2);
	myVector.push_back(8);
	myVector.push_back(14);
	myVector.push_back(22);
	myVector.push_back(24);
	int idx = linearSearch(myVector, 14); // This should return the index of where the item was found
	std::cout << "Found item at index " << idx << std::endl;
	std::cout << "Before sorting: " << std::endl;
	for (int num : myVector) {
		std::cout << num << " ";
	}
	bubbleSort(myVector);
	std::cout << std::endl << "After sorting: " << std::endl;
	for (int num : myVector) {
		std::cout << num << " ";
	}
	idx = linearSearch(myVector, 14); // This should return the index of where the item was found
	std::cout << "Found item at index " << idx << std::endl;
	int x = 1;
	std::cin >> x;
	idx = binarySearch(myVector, 4); // Should return the index where the item was found
	std::cout << "Using binary search, we found 4 at index " << idx << std::endl;
	idx = linearSearch(myVector, 4); // This should return the index of where the item was found
	std::cout << "Using linear search, we found 4 at index " << idx << std::endl;

	idx = binarySearch(myVector, 28); // Should return the index where the item was found
	std::cout << "Using binary search, we found 28 at index " << idx << std::endl;
	idx = linearSearch(myVector, 28); // This should return the index of where the item was found
	std::cout << "Using linear search, we found 28 at index " << idx << std::endl;

	//x = 5 / x;
	//std::cout << x << std::endl;
	//std::cin >> x;
}

void bubbleSort(std::vector<int> &vectorToSort) {
	// Save off the size so we don't have to compute it every time.
	int size = vectorToSort.size();

	// Loop through the list twice to do bubble sort.
	// The inner loop swaps items in the vector if needs be.
	// The outer loop makes sure we run the swaps enough times to actually be sorted.
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size - 1; j++) {
			// Do we need to swap?
			if (vectorToSort[j] > vectorToSort[j + 1]) {
				// Yes, we do.
				int temp = vectorToSort[j + 1];
				vectorToSort[j + 1] = vectorToSort[j];
				vectorToSort[j] = temp;
			}
		}
	}
}

// This should return the index of where the item was found
int linearSearch(std::vector<int> &myVect, int numToTest) {
	// loop through the vector
	for (int i = 0; i < myVect.size(); i++) {
		// if we found the item we were looking for
		if (myVect[i] == numToTest) {
			// return the index
			return i;
		}
	}
	// If we looped through the entire vector and never returned, we never found the item.
	// so return -1 as an error condition.
	return -1;
}

int binarySearch(std::vector<int> &myVect, int numToTest) {
	//if (myVect.size() < 1) {
	//	return -1;
	//}
	bool done = false;
	int start = 0;
	int end = myVect.size();
	while (!done) {
		// Get midpoint.
		int midpoint = floor((start + end / 2));

		// Special case ending (base case).
		if (end - start <= 2) {
			// check the remaining two items
			if (myVect[end] == numToTest) return end;
			if (myVect[start] == numToTest) return start;
			// if numToTest doesn't match either one, we never found the item.
			return -1;
		}
		// Check value at midpoint against numToTest.
		if (myVect[midpoint] == numToTest) {
			// if midpoint == numToTest return midpoint.
			return midpoint;
		}
		else if (myVect[midpoint] < numToTest) {
			// else if midpoint < numToTest
			// set start to midpoint
			start = midpoint;
		}
		else {
			// else
			// set end to midpoint
			end = midpoint;
		}
	}
	return -1;

}