home *** CD-ROM | disk | FTP | other *** search
/ C by Discovery (4th Edition) / C_By_Discovery_4th_Edition.tar / C_By_Discovery_4th_Edition / _DISK_ / ch6 / binsrch.c next >
C/C++ Source or Header  |  2005-06-16  |  2KB  |  66 lines
  1. /*               binsrch.c
  2.  *
  3.  *   Synopsis  - The program initializes an array at the time of
  4.  *               declaration and prompts the user to enter a value to
  5.  *               find in the array. The function bin_search() looks
  6.  *               for that value and the results of the search is
  7.  *               displayed.
  8.  *
  9.  *   Objective - To see one method of searching an array.
  10.  */
  11. /* Header files */
  12. #include <stdio.h>
  13.  
  14. /* Constant Definitions */
  15. #define ARRAY_SIZE 11
  16.  
  17. /* Function Prototypes */
  18. int bin_search( int desired_element, int array[], int first, int last );
  19. /*   PRECONDITION:  desired_element is the value to search for. 
  20.  *                  array is the array to search, first is the 
  21.  *                  index of the first element in the part of the 
  22.  *                  array to search and last is the index of the last 
  23.  *                  element in the part of the array to search.
  24.  *                  array must be sorted in increasing order.
  25.  *   POSTCONDITION: If desired_element is in array, the function 
  26.  *                  returns an index in array where desired_element 
  27.  *                  was found. If desired_element is not in the array, 
  28.  *                  the value -1 is returned.
  29.  */
  30.  
  31. int main()
  32. {
  33.      int intvar, index;
  34.      int intarray[ARRAY_SIZE] = {-21, 3, 13, 23, 37, 45, 57, 67, 77, 89, 92};
  35.      printf( "What number do you want to search for? " );
  36.      scanf ( "%d", &intvar );
  37.  
  38.      index = bin_search( intvar, intarray, 0, 10 );
  39.  
  40.      if ( index == -1 )
  41.           printf( "%d is not in the array.\n", intvar );
  42.      else
  43.           printf( "%d is in the %dth cell of the array.\n", intvar, index + 1 );
  44.  
  45.      return 0;
  46. }
  47.  
  48. /*******************************bin_search()********************/
  49.  
  50. int bin_search( int desired_element, int array[], int first, int last )
  51. {
  52.      int mid;
  53.      if ( first <= last ) {                         /* Note 1 */
  54.           mid = (first + last)/2;
  55.           if ( array[mid] > desired_element )
  56.                                                     /* Note 2 */
  57.                return(bin_search(desired_element,array, first,mid-1));
  58.           else if ( array[mid] < desired_element )
  59.                                                     /* Note 2 */
  60.                return(bin_search(desired_element,array,mid+1,last));
  61.           else 
  62.                return mid;
  63.      }
  64.      else 
  65.           return -1;                                /* Note 1 */
  66. }