fork download
copy 
  1. //Ryan Shahriyarpour   CS1A  Chapter 8   Question 4
  2. /*****************************************************************************
  3.  * 
  4.  * Charge Account Validation Modification
  5.  * 
  6.  *********************
  7.  * 
  8.  * This program lets the user enter a charge account number and determines
  9.  * whether the number is valid by checking for it in a list of 18 valid
  10.  * account numbers. It uses a BINARY SEARCH instead of a linear search.
  11.  * 
  12.  * *******************
  13.  * A binary search only works on a sorted array, so the list is first
  14.  * sorted with a SELECTION SORT. The binary search then checks the middle
  15.  * element and throws away the half of the list that cannot hold the number,
  16.  * repeating until the number is found or nothing is left to search.
  17.  * 
  18.  * INPUT
  19.  *  account  - the charge account number to check
  20.  * 
  21.  * OUTPUT    
  22.  *  A message saying whether the account number is valid or invalid
  23.  * 
  24.  ****************************************************************************/
  25.  
  26. #include <iostream>
  27. using namespace std;
  28.  
  29. // Constant for the number of valid accounts
  30. const int SIZE = 18;
  31.  
  32. // Function prototypes
  33. void selectionSort(int array[], int size);
  34. int binarySearch(const int array[], int size, int value);
  35.  
  36. int main()
  37. {
  38.     // data dictionary
  39.     int accounts[SIZE] = {          // List of valid account numbers
  40.         5658845, 4520125, 7895122, 8777541, 8451277, 1302850,
  41.         8080152, 4562555, 5552012, 5050552, 7825877, 1250255,
  42.         1005231, 6545231, 3852085, 7576651, 7881200, 4581002
  43.     };
  44.     int account;                    // Account number entered by the user
  45.     int result;                     // Index where found, or -1 if not found
  46.  
  47.     // Sort the list so a binary search can be used
  48.     selectionSort(accounts, SIZE);
  49.  
  50.     // Get the account number
  51.     cout << "Enter a charge account number: ";
  52.     cin >> account;
  53.  
  54.     // Binary search
  55.     result = binarySearch(accounts, SIZE, account);
  56.  
  57.     // Display the result
  58.     if (result == -1)
  59.         cout << "\nThat account number is invalid." << endl;
  60.     else
  61.         cout << "\nThat account number is valid." << endl;
  62.  
  63.     return 0;
  64. }
  65.  
  66. // Sorts the array into ascending order using a selection sort
  67. void selectionSort(int array[], int size)
  68. {
  69.     // data dictionary
  70.     int startScan;                  // Position being filled on this pass
  71.     int index;                      // Loop counter that scans for the smallest
  72.     int minIndex;                   // Index of the smallest value found
  73.     int minValue;                   // The smallest value found
  74.  
  75.     for (startScan = 0; startScan < size - 1; startScan++)
  76.     {
  77.         minIndex = startScan;
  78.         minValue = array[startScan];
  79.         for (index = startScan + 1; index < size; index++)
  80.         {
  81.             if (array[index] < minValue)
  82.             {
  83.                 minValue = array[index];
  84.                 minIndex = index;
  85.             }
  86.         }
  87.         array[minIndex] = array[startScan];
  88.         array[startScan] = minValue;
  89.     }
  90. }
  91.  
  92. // Returns the index of value in the sorted array, or -1 if not found
  93. int binarySearch(const int array[], int size, int value)
  94. {
  95.     // data dictionary
  96.     int first = 0;                  // First index still being searched
  97.     int last = size - 1;            // Last index still being searched
  98.     int middle;                     // Middle index of the range
  99.     int position = -1;              // Index of the match (-1 = not found)
  100.     bool found = false;             // True once the value is located
  101.  
  102.     while (!found && first <= last)
  103.     {
  104.         middle = (first + last) / 2;
  105.         if (array[middle] == value)
  106.         {
  107.             found = true;
  108.             position = middle;
  109.         }
  110.         else if (array[middle] > value)
  111.             last = middle - 1;      // Value must be in the lower half
  112.         else
  113.             first = middle + 1;     // Value must be in the upper half
  114.     }
  115.     return position;
  116. }
Success #stdin #stdout 0s 5328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Enter a charge account number: 
That account number is invalid.
https://ideone.com/6ZAt4L
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!