// TITLE: Binary search of an array
// AUTHOR: Paul Curzon, modifed from Deitel & Deitel
// DATE 23/7/2002
// DESCRIPTION:
//   This program randomly generates a series of test data of differing sizes
//   (5 - 100 positive integers) reading them into array a. 
//   It then randomly generates a search key
//   and searches the elements of the array using binary search.
//   It returns a table giving the amount of data the test was 
//   run on and the number of comparisons made.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

enum SearchResult {FOUND, NOT_FOUND};

SearchResult binarySearch(int array[], int key, int high,  int *count);
void fill_array(int array[], int sizeOfData);

const int RANGE = 200; // random data used in range 0-199

int main()
  {
     const int arraySize = 100;
     int a[arraySize];
     FILE *resultsFile;
     resultsFile = fopen("bsrch.dat", "w");  // open the file lsrrch.dat for writing ("w")

     if (resultsFile != NULL)      // file successfully opened
      {
         // seed the random number generator so it gives different
       // random numbers each time
       srand ( time (0) );


       // Table headings
       printf ("Found\t Data Size\t Comparisons Needed\n"  );
                        //\t puts in a tab character, \n a new line
       fprintf (resultsFile, "Data Size\t Found/Not found\tComparisons Needed\n"  );

       fill_array(a, arraySize);
       // Generate table for data of different sizes
       // giving number of comparisons each time
	 
	   
	   
	  int count = 0;  // number of comparisons this time
	  SearchResult result; // result of this search
	  int searchKey = rand() %RANGE;
       
	   
	   
	   result = binarySearch(a, searchKey,arraySize, &count);
	


for(int i = 0; i<arraySize; i++)
{

	
    
	if(searchKey == a[i])
	{
	printf("arraySize %d \tKEY FOUND searchkey is: %d\n",a[i],searchKey);
	
	}
	
	else

	printf("arraySize %d \tNOT FOUND search key is: %d\n" ,a[i],searchKey);
        fprintf(resultsFile, "%d  \t\t\t%d\t\t\t  %d\n",a[i],result,count);
}



	  // print results in a table
          printf("Data size%d  \t\t\tthe comparisons are %d\n",arraySize, count);
          fprintf(resultsFile, "%d  \t\t\t %d \t\t\t %d\n",arraySize,result,count);
 	
     }
   else
      fprintf(resultsFile, "File not opened\n");

   fclose(resultsFile); return 0;
    }


// generate  data in range 0-200  by doubling position and fill the
// array with it up to the given size

void fill_array(int array[], int sizeOfData)
 {

     for (int counter = 0; counter < sizeOfData; counter++)
      {
	array[counter] = counter + 1;
		
      }
 }


// A binary search function that returns the number of comparisons
// made call by value as well as a direct indication of found or not.

SearchResult binarySearch(int array[], int key,int sizeOfData, int *count)
 {
      int low = 0;
      int high = sizeOfData; 
 int mid = 0;




while(low <= high)
{

      *count = *count + 1;  //about to do a comparison

	  mid = (low + high) / 2;

	  

     
 if (array[mid] == key)
 {
  return FOUND;
 }// Key found!

if(key < array[mid])
								{
							        high = mid - 1;
							    }
										  
						        else 
								{
						             low = mid + 1;
								}

if(low > high)
{
 return NOT_FOUND;
}


}


 }