// Purpose - a binary search

#include <iostream>
#include <cstdlib>
#include <ctime> 
using namespace std;

const int ARRAY_SIZE = 8;

int binarySearch(int numbers[], int lengthOfArray, int key);
void selectionSort(int numbers[], int lengthOfArray);

int main()
{
	int numbers[ARRAY_SIZE];	// array to be sorted
	int i = 0;			// loop variable
	int num = 0;			// key value
	int position = -1;		// position of key value in array, -1 if not found.
	
	srand(time(0));
	
	for (i = 0; i < ARRAY_SIZE; i++)	// generating numbers between 1 and 100
	{
		numbers[i] = rand() % 100 + 1;
	}

	selectionSort(numbers, ARRAY_SIZE);		// sorting the array with a selection sort
							// a binary search requires that the array already be sorted

	cout << "The numbers in sorted, ascending order are: " << endl;
	
	for (i = 0; i < ARRAY_SIZE; i++)			// neatly displaying the array
	{
		cout << numbers[i] << '\t';
	}
	
	cout << "\nEnter a number that you would like to search for: ";
	cin >> num;

	position = binarySearch(numbers, ARRAY_SIZE, num);
	
	if (position != -1)
	{
		cout << "The number was found in position " << position << endl;
	}
	else
	{
		cout << "The number was not found." << endl;
	}

	return 0;
}// end of main

int binarySearch(int numbers[], int lengthOfArray, int key)
{
	int low = 0;			// lower end of search range
	int high = lengthOfArray - 1;	// upper end of search range
	int mid = 0;			// middle of search range
	bool found = false;		// key found or not
	int location = -1;		// position of key value in array
	
	while ((low <= high) && !found)
	{
		mid = (low + high) / 2;
	
		if (key == numbers[mid])
		{
			found = true;
			location = mid;
		}
		else if (key < numbers[mid])
		{
			high = mid - 1;
		}
		else if (key >numbers[mid] )
		{
			low = mid + 1;
		}

	}
	return location;
}// end of binarySearch

void selectionSort(int numbers[], int lengthOfArray)
{
	int i = 0;			// loop variable
	int j = 0;			// loop variable
	int temp = 0;			// temp variable used in swap
	int minElement = 0;		// current smallest value
	int positionOfMinElement = 0;	// smallest element found so far
	
	for (i = 0; i < lengthOfArray; i++)
	{
		minElement = numbers[i];
		positionOfMinElement = i;
		
		for (j = i + 1; j < lengthOfArray; j++)
		{
		
			if (numbers[j] < minElement)
			{
				minElement = numbers[j];
				positionOfMinElement = j;
			}
		}

		temp = numbers[i];			// swapping out of order elements
		numbers[i] = numbers[positionOfMinElement];
		numbers[positionOfMinElement] = temp;
	}

}// end of sort