/* --------------------------------------------------------------------- ** Binary search. ** Figures 21.5: The binary search program. ** 21.6: Setting up the data structures. ** 21.7: Getting and checking the data. ** 21.8: The binary search function, bin_search(). (recursive). ** ** The data in the input file must be sorted in ascending order. ** --------------------------------------------------------------------- */ #include "tools.h" #define NOT_FOUND -1 typedef struct { int* data; int n; int max; } data_pack; void setup( data_pack* spec, stream* infile ); void get_data( data_pack* searchp, stream instream ); void check_data( data_pack search ); int bin_search( int data[], int left, int right, int key ); /* ------------------------------------------------------------------ */ void main( void ) { stream fin; /* Stream for the input file. */ data_pack search; /* Array data. */ int key; /* Number to search for. */ int slot; /* Position at which key is found. */ int stream_status; /* For scanf()'s return value. */ banner(); puts( "\n Find a key value in an array of integers." ); setup ( &search, &fin ); get_data( &search, fin ); check_data( search ); printf( " %i data items read; ready to search.\n", search.n ); puts( "\n Enter numbers to search for; period to quit." ); for(;;) { printf( " What number do you wish to find? " ); stream_status = scanf( "%i", &key ); if (stream_status < 1) break; slot = bin_search( search.data, 0, search.n - 1, key ); if (slot == NOT_FOUND) printf( " Key value %i is not in table.\n\n", key ); else printf( " Key value %i was found in slot %i.\n\n", key, slot ); } bye(); } /* --------------------------------------------------------------------- ** Construct and initialize a data-pack and an input stream. ** Read (from user) name of input file and open it. ** Allocate memory for MAX data items. Errors are fatal. */ #define MAX 1000 void setup( data_pack* spec, stream* infile ) { char filename[80]; /* For name of input file */ spec->max = MAX; /* Space for MAX items. */ spec->n = 0; /* Currently empty. */ spec->data = malloc( MAX * sizeof(int) ); if (spec->data == NULL) fatal( " Error: not enough memory for %i ints\n", MAX ); printf( " Enter name of data file to be searched: " ); scanf( "%79s",filename ); *infile = fopen ( filename, "r" ); if (*infile == NULL) fatal( " Error: couldn't open input file %s\n", filename ); } /* --------------------------------------------------------------------- ** Read up to max integers from input stream and store in array. */ void get_data( data_pack* searchp, stream instream ) { int stream_status; /* For scanf()'s return value. */ int* cursor = searchp->data; /* Scanning pointer. */ int* end = cursor + searchp->max; /* An off-board sentinel */ for( ; cursorn = cursor-searchp->data; /* Actual # of items read. */ } /* --------------------------------------------------------------------- ** Make sure that the data are in ascending sorted order. */ void check_data( data_pack search ) { int k;/* */ int* head = search.data; /* */ for (k = 1; k < search.n; ++k) { if (head[k] < head[k-1]) fatal( " Cannot continue, data in file are not sorted." ); } } /* --------------------------------------------------------------------- ** Search n values in data array for the key */ int bin_search( int data[], int left, int right, int key ) { int mid = (left + right) / 2; /* Compute middle of search interval */ /* Base cases: (1) we found it or (2) it's not there */ if (data[mid] == key) return mid; if (left >= right) return NOT_FOUND; /* Recursion: search a smaller array */ if (key < data[mid]) return bin_search( data, left, mid - 1, key ); else return bin_search( data, mid + 1, right, key ); } /* Output ------------------------- Displayed on screen: ---------- / Find a key value in an array of integers. Please enter name of data file to be searched: fake.in Error: couldn't open input file fake.in Error exit; press '.' and 'Enter' to continue. ------------------------------------------------------------------- Find a key value in an array of integers. Please enter name of data file to be searched: mixedup.dat Cannot continue, data in file is not sorted. Error exit; press '.' and 'Enter' to continue. ------------------------------------------------------------------- Find a key value in an array of integers. Please enter name of data file to be searched: binserch.dat 17 data items read; ready to search. Enter numbers to search for; period to quit. What number do you wish to find? 2 Key value 2 is not in table. What number do you wish to find? 24 Key value 24 was found in slot 0. What number do you wish to find? 276 Key value 276 was found in slot 4. What number do you wish to find? 967 Key value 967 was found in slot 16. What number do you wish to find? 270 Key value 270 is not in table. What number do you wish to find? 1000 Key value 1000 is not in table. What number do you wish to find? . Normal termination. ------------------------------------------------------------------- Find a key value in an array of integers. Please enter name of data file to be searched: sorted.dat Ready to read the file. 1000 data items read; ready to search. Enter numbers to search for; period to quit. What number do you wish to find? 0 Key value 0 was found in slot 0. What number do you wish to find? 1899 Key value 1899 was found in slot 996. What number do you wish to find? 35 Key value 35 was found in slot 16. What number do you wish to find? 34 Key value 34 is not in table. What number do you wish to find? . Normal termination. */