fork download
copy 
  1. // Torrez, Elaine                       CS1A                         Chapter 8 P. 487, #4
  2. /********************************************************************************************
  3.  * 
  4.  * SORT AND SEARCH CHARGE ACCOUNT NUMBER
  5.  * 
  6.  * ------------------------------------------------------------------------------------------
  7.  * This program determines whether a user-entered charge account number is valid.
  8.  * It first sorts a fixed list of valid account numbers using the selection sort
  9.  * algorithm. Then, it uses the binary search algorithm to determine whether the
  10.  * entered number exists in the list. 
  11.  * 
  12.  * If the number is found, the program reports that the account number is valid;
  13.  * otherwise, it reports that it is invalid.
  14.  * 
  15.  * Input validation ensures that the user enters a positive 7-digit number before
  16.  * performing the search.
  17.  * ------------------------------------------------------------------------------------------
  18.  * 
  19.  * INPUT
  20.  *    userNum   : Charge account number entered by the user
  21.  * 
  22.  * OUTPUT
  23.  *    Message stating whether the account number is valid or invalid
  24.  * 
  25.  ********************************************************************************************/
  26.  
  27. #include <iostream>
  28. #include <iomanip>
  29. using namespace std;
  30.  
  31. // Function prototypes
  32. void selectionSort(int array[], int size);
  33. int  binarySearch(const int array[], int size, int value);
  34.  
  35. int main()
  36. {
  37.     const int SIZE = 18;                     // Number of account numbers
  38.     int accounts[SIZE] = {                   // List of valid account numbers
  39.         5658845, 4520125, 7895122, 8777541, 8451277, 1302850,
  40.         8080152, 4562555, 5552012, 5050552, 7825877, 1250255,
  41.         1005231, 6545231, 3852085, 7576651, 7881200, 4581002
  42.     };
  43.  
  44.     int userNum;                             // Number entered by the user
  45.     int position;                            // Position if found
  46.  
  47.     // ----------------------------------------------------
  48.     // INPUT VALIDATION
  49.     // ----------------------------------------------------
  50.     cout << "Enter a 7-digit charge account number: ";
  51.     cin >> userNum;
  52.  
  53.     while (cin.fail() || userNum < 1000000 || userNum > 9999999)
  54.     {
  55.         cin.clear();
  56.         cin.ignore(1000, '\n');
  57.         cout << "ERROR: Enter a VALID 7-digit positive number: ";
  58.         cin >> userNum;
  59.     }
  60.  
  61.     // ----------------------------------------------------
  62.     // PROCESSING: Sort the array, then search it
  63.     // ----------------------------------------------------
  64.     selectionSort(accounts, SIZE);                   // Sort array in ascending order
  65.     position = binarySearch(accounts, SIZE, userNum); // Perform binary search
  66.  
  67.     cout << endl;
  68.     cout << fixed << setprecision(0);
  69.  
  70.     // ----------------------------------------------------
  71.     // OUTPUT RESULTS
  72.     // ----------------------------------------------------
  73.     if (position != -1)
  74.         cout << "The account number is VALID." << endl;
  75.     else
  76.         cout << "The account number is INVALID." << endl;
  77.  
  78.     return 0;
  79. }
  80.  
  81. /********************************************************************************************
  82.  * SELECTION SORT
  83.  * ------------------------------------------------------------------------------------------
  84.  * This function sorts an integer array in ascending order using the selection sort
  85.  * algorithm.
  86.  ********************************************************************************************/
  87. void selectionSort(int array[], int size)
  88. {
  89.     int minIndex, minValue;
  90.  
  91.     for (int start = 0; start < size - 1; start++)
  92.     {
  93.         minIndex = start;
  94.         minValue = array[start];
  95.  
  96.         for (int index = start + 1; index < size; index++)
  97.         {
  98.             if (array[index] < minValue)
  99.             {
  100.                 minValue = array[index];
  101.                 minIndex = index;
  102.             }
  103.         }
  104.  
  105.         // Swap values
  106.         array[minIndex] = array[start];
  107.         array[start] = minValue;
  108.     }
  109. }
  110.  
  111. /********************************************************************************************
  112.  * BINARY SEARCH
  113.  * ------------------------------------------------------------------------------------------
  114.  * This function performs a binary search on a sorted integer array.
  115.  * It returns the index of the value if found, or -1 if the value is not in the array.
  116.  ********************************************************************************************/
  117. int binarySearch(const int array[], int size, int value)
  118. {
  119.     int first = 0;
  120.     int last = size - 1;
  121.     int middle;
  122.     int position = -1;
  123.     bool found = false;
  124.  
  125.     while (!found && first <= last)
  126.     {
  127.         middle = (first + last) / 2;
  128.  
  129.         if (array[middle] == value)
  130.         {
  131.             found = true;
  132.             position = middle;
  133.         }
  134.         else if (array[middle] > value)
  135.             last = middle - 1;
  136.         else
  137.             first = middle + 1;
  138.     }
  139.  
  140.     return position;
  141. }
  142.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
5658845
stdout
copy 
Enter a 7-digit charge account number: 
The account number is VALID.
https://ideone.com/0yjTqH
language:
C++ (gcc 8.3)
created:
3 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!