/* 
Run! LIVE!

   Note: The name of an array is the same as &array[ 0 ] 
*/

// search.cpp cis205 03/14/02

/*
tracks number of comparisons needed by a
linear search and a binary search of a 
sorted array to find the cell with the value 
SOUGHT in a CELLS cell array containing 
the values 0..CELLS - 1

	Example Output:

Found 250 after 250 linear search attempts of the 500 cell array.
Found 250 after 8 binary search attempts of the 500 cell array.

*/

#define FALSE 0
#define TRUE !FALSE

#define CELLS 500
#define SOUGHT 250

#include <iostream.h>

// prototypes
void fillArray( int []);
void sortAscending(int []);
int linearSearch(int, int []);
int binarySearch(int, int []);


int main(void)
{
	// command and control center

	int intArray[CELLS];
	int attempts;
	int intSought = SOUGHT;

	fillArray(intArray);

	attempts = linearSearch(intSought, intArray);
	if(attempts == 0)
	{
		cout << "Could not find " << intSought << " in the array using a linear search." << endl;
	}
	else
	{
		cout << "Found " << intSought << " after " << attempts << " linear search attempts of the " << CELLS << " cell array." << endl;
	}


	attempts = binarySearch(intSought, intArray);
	if(attempts == 0)
	{
		cout << "Could not find " << intSought << " in the array using a binary search." << endl;
	}
	else
	{
		cout << "Found " << intSought << " after " << attempts << " binary search attempts of the " << CELLS << " cell array." << endl;
	}

	return 0;

}

void fillArray(int a[])
{
	for(int i = 0; i < CELLS; i++)
	{
		a[i] = i;
	}
}

void sortAscending(int a[])
{

	for(int pass = 0; pass < CELLS - 1; pass++)
	{
		for(int i = 0; i < CELLS - 1; i++)
		{
			if(a[i] > a[i + 1])
			{
				int temp = a[i];
				a[i] = a[i + 1];
				a[i + 1] = temp;
			}
		}
	}
}

int linearSearch(int needle, int haystack[])
{
	int found = FALSE;
	int i = 0;
	int comparisons = 0;

	while(found == FALSE && i < CELLS)
	{
		comparisons++;
		i++;
		if(haystack[i] == needle)
		{
			found = TRUE;
		}		
	}

	if(found == FALSE)
	{
		comparisons = 0;
	}

	return comparisons;
}


int binarySearch(int needle, int haystack[])
{

	int comparisons = 0;

	int first = 0;
	int last = CELLS - 1;
	int middle;
	int found = FALSE;

	sortAscending(haystack);

	while(found == FALSE && first <= last)
	{
		middle = (first + last) / 2; // integer division
		comparisons++;
		if(haystack[middle] == needle)
		{
			found = TRUE;
		}
		else if (haystack[middle] > needle)
		{
			last = middle - 1;
		}
		else
		{
			first = middle + 1;
		}
	}
	
	if(found == FALSE)
	{
		comparisons = 0; 
	}

	return comparisons;

}