fork download 
  1. //Ryan Shahriyarpour   CS1A  Chapter 8   Question 8
  2. /*****************************************************************************
  3.  * 
  4.  * Search Benchmarks
  5.  * 
  6.  *********************
  7.  * 
  8.  * This program stores 20 sorted integers in an array and lets the user
  9.  * pick a value to look for. The value is located twice, once with a linear
  10.  * search and once with a binary search. Each search counts how many
  11.  * comparisons it makes so the two methods can be compared.
  12.  * 
  13.  * *******************
  14.  * One comparison is counted each time an array element is checked against
  15.  * the value being searched for.
  16.  *  Linear search - checks the elements one at a time from the start.
  17.  *  Binary search - checks the middle of the remaining range each time.
  18.  *                  (The array has to be sorted, and this one is.)
  19.  * 
  20.  * INPUT
  21.  *  searchValue  - the integer to search for
  22.  * 
  23.  * OUTPUT    
  24.  *  The number of comparisons used by the linear search
  25.  *  The number of comparisons used by the binary search
  26.  * 
  27.  ****************************************************************************/
  28.  
  29. #include <iostream>
  30. using namespace std;
  31.  
  32. // Constant for the number of array elements
  33. const int SIZE = 20;
  34.  
  35. // Function prototypes (each returns the index found, or -1 if not found)
  36. int linearSearch(const int array[], int size, int value, int &comparisons);
  37. int binarySearch(const int array[], int size, int value, int &comparisons);
  38.  
  39. int main()
  40. {
  41.     // data dictionary
  42.     int numbers[SIZE] = {           // Sorted array of integers
  43.          3,  7, 12, 18, 24, 29, 35, 41, 46, 52,
  44.         58, 63, 69, 74, 80, 86, 91, 95, 98, 103
  45.     };
  46.     int searchValue;                // Value the user wants to find
  47.     int position;                   // Index returned by a search
  48.     int linearCount = 0;            // Comparisons made by the linear search
  49.     int binaryCount = 0;            // Comparisons made by the binary search
  50.  
  51.     // Get the value to search for
  52.     cout << "Array: 3 7 12 18 24 29 35 41 46 52 "
  53.          << "58 63 69 74 80 86 91 95 98 103" << endl;
  54.     cout << "Enter a value to search for: ";
  55.     cin >> searchValue;
  56.  
  57.     // Run both searches
  58.     position = linearSearch(numbers, SIZE, searchValue, linearCount);
  59.     binarySearch(numbers, SIZE, searchValue, binaryCount);
  60.  
  61.     // Display the results
  62.     if (position == -1)
  63.         cout << "\n" << searchValue << " was not found in the array." << endl;
  64.     else
  65.         cout << "\n" << searchValue << " was found at index "
  66.              << position << "." << endl;
  67.  
  68.     cout << "Linear search comparisons: " << linearCount << endl;
  69.     cout << "Binary search comparisons: " << binaryCount << endl;
  70.  
  71.     return 0;
  72. }
  73.  
  74. // Linear search; comparisons goes up by one for each element checked
  75. int linearSearch(const int array[], int size, int value, int &comparisons)
  76. {
  77.     // data dictionary
  78.     int index;                      // Loop counter
  79.     int position = -1;              // Index of the match (-1 = not found)
  80.  
  81.     for (index = 0; index < size; index++)
  82.     {
  83.         comparisons++;
  84.         if (array[index] == value)
  85.         {
  86.             position = index;
  87.             break;
  88.         }
  89.     }
  90.     return position;
  91. }
  92.  
  93. // Binary search; comparisons goes up by one for each middle element checked
  94. int binarySearch(const int array[], int size, int value, int &comparisons)
  95. {
  96.     // data dictionary
  97.     int first = 0;                  // First index still being searched
  98.     int last = size - 1;            // Last index still being searched
  99.     int middle;                     // Middle index of the range
  100.     int position = -1;              // Index of the match (-1 = not found)
  101.     bool found = false;             // True once the value is located
  102.  
  103.     while (!found && first <= last)
  104.     {
  105.         middle = (first + last) / 2;
  106.         comparisons++;
  107.         if (array[middle] == value)
  108.         {
  109.             found = true;
  110.             position = middle;
  111.         }
  112.         else if (array[middle] > value)
  113.             last = middle - 1;
  114.         else
  115.             first = middle + 1;
  116.     }
  117.     return position;
  118. }
Success #stdin #stdout 0s 5348KB
comments (?)
stdin 
Standard input is empty
stdout 
Array: 3 7 12 18 24 29 35 41 46 52 58 63 69 74 80 86 91 95 98 103
Enter a value to search for: 
5306 was not found in the array.
Linear search comparisons: 20
Binary search comparisons: 5
https://ideone.com/4cVb0H
language:
C++ (gcc 8.3)
created:
8 hours 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!