home *** CD-ROM | disk | FTP | other *** search
/ C Programming Starter Kit 2.0 / SamsPublishing-CProgrammingStarterKit-v2.0-Win31.iso / tybc4 / array6.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1993-03-26  |  4.3 KB  |  163 lines
  1. // C++ program that searches arrays using the linear
  2. // and binary searches methods
  3.  
  4. #include <iostream.h>
  5.               
  6. const int MAX = 10;              
  7. const int TRUE = 1;
  8. const int FALSE = 0;
  9. const int NOT_FOUND = -1;
  10.  
  11. int obtainNumData()
  12. {
  13.   int m;
  14.   do { // obtain number of data points
  15.     cout << "Enter number of data points [2 to "
  16.         << MAX << "] : ";
  17.     cin >> m;
  18.     cout << "\n";
  19.   } while (m < 2 || m > MAX);
  20.   return m;
  21. }
  22.  
  23. void inputArray(int intArr[], int n)
  24. {              
  25.   // prompt user for data
  26.   for (int i = 0; i < n; i++) {
  27.     cout << "arr[" << i << "] : ";
  28.     cin >> intArr[i];
  29.   }
  30. }
  31.                  
  32. void showArray(int intArr[], int n)
  33. {              
  34.   for (int i = 0; i < n; i++) {
  35.     cout.width(5);
  36.     cout << intArr[i] << " ";
  37.   }
  38.   cout << "\n";
  39. }                       
  40.  
  41. void sortArray(int intArr[], int n)   
  42. // sort the first n elements of array intArr
  43. // using the Comb sort method
  44. {
  45.   int offset, temp, inOrder;
  46.   
  47.   offset = n;      
  48.   do {                                       
  49.     offset = (8 * offset) / 11;
  50.     offset = (offset == 0) ? 1 : offset;
  51.     inOrder = TRUE;
  52.     for (int i = 0, j = offset; i < (n - offset); i++, j++) {
  53.       if (intArr[i] > intArr[j]) {
  54.         inOrder = FALSE;
  55.         temp = intArr[i];
  56.         intArr[i] = intArr[j];
  57.         intArr[j] = temp;
  58.       }
  59.     }
  60.   } while (!(offset = 1 && inOrder == TRUE));
  61. }
  62.  
  63. int linearSearch(int searchVal, int intArr[], int n)
  64. // perform linear search to locate the first
  65. // element in array intArr that matches the value
  66. // of searchVal
  67. {
  68.   int notFound = TRUE;
  69.   int i = 0;
  70.   // search through the array elements
  71.   while (i < n && notFound) 
  72.     // no match?
  73.     if (searchVal != intArr[i])
  74.       i++; // increment index to compare the next element
  75.     else 
  76.       notFound = FALSE; // found a match
  77.   // return search outcome
  78.   return (notFound == FALSE) ? i : NOT_FOUND;
  79. }                            
  80.                                              
  81. int binarySearch(int searchVal, int intArr[], int n)
  82. // perform binary search to locate the first
  83. // element in array intArr that matches the value
  84. // of searchVal
  85. {
  86.   int median, low, high;
  87.                                         
  88.   // initialize the search range                                        
  89.   low = 0;
  90.   high = n - 1;
  91.   // search in array
  92.   do {              
  93.     // obtain the median index of the current search range
  94.     median = (low + high) / 2;                            
  95.     // update search range
  96.     if (searchVal > intArr[median])
  97.       low = median + 1;
  98.     else
  99.       high = median - 1;
  100.   } while (!(searchVal == intArr[median] || low > high));
  101.   // return search outcome
  102.   return (searchVal == intArr[median]) ? median : NOT_FOUND;
  103. }                            
  104.                           
  105. void searchInUnorderedArray(int intArr[], int n)
  106. // manage the linear search test
  107. {
  108.   int x, i;
  109.   char c;
  110.   // perform linear search
  111.   cout << "Search in unordered array? (Y/N) ";
  112.   cin >> c;
  113.   while (c == 'Y' || c == 'y') {
  114.     cout << "Enter search value : ";
  115.     cin >> x;
  116.     i = linearSearch(x, intArr, n);
  117.     if (i != NOT_FOUND)
  118.       cout << "Found matching element at index " << i << "\n";
  119.     else
  120.       cout << "No match found\n";
  121.     cout << "Search in unordered array? (Y/N) ";
  122.     cin >> c;
  123.   }  
  124. }                          
  125.  
  126. void searchInSortedArray(int intArr[], int n)
  127. // manage the binary search test
  128. {
  129.   int x, i;
  130.   char c;
  131.   // perform binary search
  132.   cout << "Search in sorted array? (Y/N) ";
  133.   cin >> c;
  134.   while (c == 'Y' || c == 'y') {
  135.     cout << "Enter search value : ";
  136.     cin >> x;
  137.     i = binarySearch(x, intArr, n);
  138.     if (i != NOT_FOUND)
  139.       cout << "Found matching element at index " << i << "\n";
  140.     else
  141.       cout << "No match found\n";
  142.     cout << "Search in sorted array? (Y/N) ";
  143.     cin >> c;
  144.   }
  145. }
  146.                                              
  147. main()
  148. {          
  149.   int arr[MAX];
  150.   int n;
  151.                                 
  152.   n = obtainNumData();                                
  153.   inputArray(arr, n);
  154.   cout << "Unordered array is:\n";
  155.   showArray(arr, n);
  156.   searchInUnorderedArray(arr, n);
  157.   sortArray(arr, n);
  158.   cout << "\nSorted array is:\n";
  159.   showArray(arr, n);                                  
  160.   searchInSortedArray(arr, n);
  161.   return 0;
  162. }
  163.