fork download 
  1. //Cameron Pham             CS1A                       Chapter 8, p. 488, #8
  2. //
  3. /******************************************************************************
  4. * SEARCH FOR BENCHMARKS
  5. * ______________________________________________________________________________
  6. * This program demonstrates and compares two sorting methods. It uses two 
  7. * identical arrays of eight integers, displays the contents of each array, and 
  8. * sorts them. After each pass of both sorting algorithms, the program displays 
  9. * the updated array.
  10. * ______________________________________________________________________________
  11. * INPUT
  12. * Number		// Number that is being searched for
  13. * 
  14. * OUTPUT
  15. * Linear		// Amount of linear search comparisons
  16. * Binary		// Amount of binary search comparisons
  17. *******************************************************************************/
  18. #include <iostream>
  19. using namespace std;
  20. // Function prototypes
  21. int linearSearch(const int [], int, int, int &);
  22. int binarySearch(const int [], int, int, int &);
  23. int main()
  24. {
  25.     // Initialize Variables
  26.     const int SIZE = 20;
  27.     int numbers[SIZE] =
  28.     {
  29.         10, 15, 20, 25, 30, 35, 40, 45, 50, 55,
  30.         60, 65, 70, 75, 80, 85, 90, 95, 100, 105
  31.     };
  32.     int searchValue;           // Value to search for
  33.     int linearComparisons = 0; // Number of linear search comparisons
  34.     int binaryComparisons = 0; // Number of binary search comparisons
  35.     int linearResult;          // Result of linear search
  36.     int binaryResult;          // Result of binary search
  37.     // Ask the user for a value to search for
  38.     cout << "Enter an integer to search for: ";
  39.     cin >> searchValue;
  40.     // Call the linear search function
  41.     linearResult = linearSearch(numbers, SIZE, searchValue,
  42.                                 linearComparisons);
  43.     // Call the binary search function
  44.     binaryResult = binarySearch(numbers, SIZE, searchValue,
  45.                                 binaryComparisons);
  46.     // Display the search results
  47.     cout << "\nSearch Results" << endl;
  48.     cout << "------------------------------" << endl;
  49.     if (linearResult != -1)
  50.     {
  51.         cout << "Value found: " << searchValue << endl;
  52.         cout << "Linear search comparisons: "
  53.              << linearComparisons << endl;
  54.         cout << "Binary search comparisons: "
  55.              << binaryComparisons << endl;
  56.     }
  57.     else
  58.     {
  59.         cout << "Value was not found in the array." << endl;
  60.         cout << "Linear search comparisons: "
  61.              << linearComparisons << endl;
  62.         cout << "Binary search comparisons: "
  63.              << binaryComparisons << endl;
  64.     }
  65.     return 0;
  66. }
  67. // Function to perform a linear search
  68. int linearSearch(const int array[], int size, int value,
  69.                  int &comparisons)
  70. {
  71.     for (int count = 0; count < size; count++)
  72.     {
  73.         comparisons++;
  74.         if (array[count] == value)
  75.         {
  76.             return count;
  77.         }
  78.     }
  79.     return -1;
  80. }
  81. // Function to perform a binary search
  82. int binarySearch(const int array[], int size, int value,
  83.                  int &comparisons)
  84. {
  85.     int first = 0;
  86.     int last = size - 1;
  87.     int middle;
  88.     while (first <= last)
  89.     {
  90.         middle = (first + last) / 2;
  91.         comparisons++;
  92.         if (array[middle] == value)
  93.         {
  94.             return middle;
  95.         }
  96.         else if (array[middle] > value)
  97.         {
  98.             last = middle - 1;
  99.         }
  100.         else
  101.         {
  102.             first = middle + 1;
  103.         }
  104.     }
  105.     return -1;
  106. }
Success #stdin #stdout 0s 5348KB
comments (?)
stdin 
5
stdout 
Enter an integer to search for: 
Search Results
------------------------------
Value was not found in the array.
Linear search comparisons: 20
Binary search comparisons: 4
https://ideone.com/6fjKqU
Chapter 8, p. 488, #8
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!