binarysearch.c

#include <stdio.h>
#include <stdbool.h>
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 *								       *
 *								       *
 *	This program demonstrates how subscripted variables are used   *
 *	It uses 2 variables:					       *
 *		matrix[10]  -  a 10 element subscripted variable       *
 * 				also known as an array.  The index     *
 *				values go from 0 -9.		       *
 *		counter - The counter used in the iteration (loop)     *
 *				This variable is both the counter for  *
 *				the loop and the index to the matrix   *
 *  	infile - The file of 10 numbers we read in to load the matrix  *
 *      MatrixNumberFile is the data file we are reading (10 numbers)  *
 *	Note:  The matrix is pre-loaded in the declaration 	       *
 *								       *
 *	Written as a class example 7/14/21 			       *
 *		by Doc G.					       *
 *								       *
 *		Modifications:  none				       *
 *								       *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
*/

int main()
{
  int matrix[100];
  int counter;
  int counter2 = 0; // counter for sorting loop
  int first;        // Initial matrix position to compate
  int second;       // Next matrix positon to compare w/ first
  int swapped;      // Indicator tat the array is out of order
  int holdum;       // variable to hold the first value when swapping
  int MaxArray;     // The maximum number of array elements (stop sort and search)
  int bottom;       // Counter to make sure we processed the entire file
  int FindMe;       // Number to search for
  int Top;          // Top of search list
  int Middle;       // Middle of search, what we compare against
  int Bottom;       // Bottom of search area
  int hold;
  bool Found; // switch for finding the sought value

  FILE *infile = fopen("NumbersToSort.txt", "r");          // Open to file read numbers
  FILE *outfile = fopen("SortedNumbersToSearch.txt", "w"); // Open file to write

  for (counter = 0; counter < 100; counter++)
  {
    fscanf(infile, "%d", &matrix[counter]); // Read from data file
    if (feof((infile)))                     // Test for End Of File
    {
      break; //  Get out of loop on End Of File
    }

    // printf("Counter = %d, Value = %d,\n",counter, matrix[counter]);
    //  The preceeding is a handy debug print

  } // End of loop to fill the array
  // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
  //		Next step, sort the array					*
  // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

  MaxArray = counter;                              // get a maximum length of the array
  for (counter = 0; counter < MaxArray; counter++) // loop through array scanning
  {
    for (counter2 = 0; counter2 < MaxArray - 1; counter2++) //check for order
    {
      if (matrix[counter2] > matrix[counter2 + 1])
      {
        holdum = matrix[counter2];
        matrix[counter2] = matrix[counter2 + 1];
        matrix[counter2 + 1] = holdum;
      } // End of If block

    } // End of inner loop

  } // End of outer loop

  // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
  //		Next step, dump the array		*
  // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
  for (counter = 0; counter < MaxArray; counter++)
  {
    printf("Matrix value matrix[%d]s= %d\n", counter, matrix[counter]);
  } // End of matrix dump loop

  // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
  //		Next step, write the array to a file so we have it saved
  // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

  for (counter = 0; counter < MaxArray; counter++)
  {
    fprintf(outfile, " %d \n", matrix[counter]);
  } // End of write file loop

  // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
  //		Next step, let's see if we can search it
  // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

  Found = false;
  printf("In the search loop \n");
  printf("What number would you like to find >> ");
  printf("One step past the read\n");
  scanf("%d", &FindMe);
  // Start the search
  Top = 0;
  printf("Top = %i\n", Top);
  Bottom = MaxArray;
  Middle = MaxArray / 2;
  while (!Found)
  {
    printf("Top %i, Middle %i, Bottom %i\n", Top, Middle, Bottom);
    if (FindMe == matrix[Middle])
      Found = true;
    else if (FindMe > matrix[Middle])
    { // Target is in lower half
      Top = Middle;
      Middle = ((Bottom - Top) / 2) + Top;
    }
    else
    { // Target is in upper half
      Bottom = Middle;
      Middle = (Bottom - Top) / 2;
    }
  } // End of while loop
  printf("Top - %d, Middle = %d, Bottom = %d\n", Top, Middle, Bottom);
  printf("The number %d was found at position %d\n", FindMe, Middle);
  fclose(infile);
} // End of main()