/*****************************************************************************
*       Creates a random array of ints, and searches for a random int        *
*       using the binary search.                                             *
*       Inputed: <none>                                                      *
*       Outputed: mainarray, search_int                                      *
*       Written: August 06, 2002                                             *
*       By: Ronald Roberts                                                   *
*****************************************************************************/

/*  ***************NOTE***************
	THE BINARY SEARCH ALGORITHM HAS
	BEEN RENAMED TO "BINARY_SEARCH_0"
	BECAUSE OF A NAMING CONFILCT WITH 
	A BUILT IN FUNCTION DEFINITION.
	**********************************
*/

/* Compiler Directives */
#include <iostream.h>
#include <iomanip.h>
#include <math.h>
#include <Stdlib.h>
#include <time.h>

/* Bubble Sort Algorithm */
void bubble_sort_ascending (int array[], int arrayLength);
void bubble_sort_ascending (int array[], int arrayLength)
	{
		int i, j, flag=1;
		int temp;
		for (i=1; (i<=arrayLength) && flag; i++)
			{
				flag =0;
				for (j=0; j< (arrayLength - i); j++)
					{
						if (array[j+1] < array [j])
							{
								temp=array[j+1];
								array[j+1]=array[j];
								array[j]=temp;
								flag=1;
							}
					}
			}			
	}
	
/* Random Number Function */
double randomfunction(int modulator, double shifter);
double randomfunction(int modulator, double shifter)
	{
		return rand()%modulator+shifter;
	}
	
	
/* Binary Search Algorithm */
void binary_search_0(int x[], int lowerbound, int upperbound, int search_num);
void binary_search_0(int x[], int lowerbound, int upperbound, int search_num)
	{
		int search_pos;
		int compare_count=1;
		search_pos=(lowerbound+upperbound)/2;
		while((x[search_pos] !=search_num) && (lowerbound <= upperbound))
			{
				compare_count++;
				if (x[search_pos] > search_num)
					{
						upperbound=search_pos-1;
					}
				else
					{
						lowerbound=search_pos+1;
					}
				search_pos=(lowerbound+upperbound)/2;
			}
		if (lowerbound <= upperbound)
			{
				cout<<"A binary search found the number in "<<compare_count<< "comparisons.\n";
			}
		else
			{
				cout<< "Number not found by binary search after "<<compare_count<< " comparisons.\n";
			}
	}
	

/* Main Code */
int main()
	{	
		const int array_num=20;
		int mainarray[array_num]={0}, flag=0, search_int=0;
		srand((unsigned)time(NULL));
		cout<<"Array: ";
		for (int i=0; i<array_num; i++)
			{
				mainarray[i]=randomfunction(50, 1);
				cout<<mainarray[i]<<" ";
			}
		bubble_sort_ascending(mainarray, 20);
		cout<<endl<<"Ordered Array: ";
		for (int i=0; i<array_num; i++)
			{
				cout<<mainarray[i]<<" ";
			}
		search_int=randomfunction(50, 1);
		cout<<endl<<"Search Number: "<<search_int<<endl;
		binary_search_0(mainarray, 0, 19, search_int);
		return 0;
	}
		
/* Results */
/*
Array: 7 32 40 42 10 23 46 30 19 24 45 12 31 5 14 17 24 47 3 33 
Ordered Array: 3 5 7 10 12 14 17 19 23 24 24 30 31 32 33 40 42 45 46 47 
Search Number: 26
Number not found by binary search after 5 comparisons.
*/