fork download
copy 
  1. // Torrez, Elaine                       CS1A                         Chapter 8 P. 487, #3
  2. /********************************************************************************************
  3.  * 
  4.  * SEARCH LOTTERY WINNER USING BINARY SEARCH
  5.  * 
  6.  * ------------------------------------------------------------------------------------------
  7.  * This program determines whether any of a buyer's 10 lottery tickets is a winner.
  8.  * The program stores a fixed list of 10 "lucky" 5-digit combinations in a sorted
  9.  * integer array. It then asks the user to enter this week's winning 5-digit number
  10.  * and uses the binary search algorithm to determine whether any ticket matches.
  11.  * If a match is found, the program reports that the player has a winning ticket;
  12.  * otherwise, it reports that none of the tickets is a winner this week.
  13.  * ------------------------------------------------------------------------------------------
  14.  * 
  15.  * INPUT
  16.  *    winningNum : This week's winning 5-digit lottery number
  17.  * 
  18.  * OUTPUT
  19.  *    Message stating whether the player has a winning ticket or not
  20.  * 
  21.  ********************************************************************************************/
  22.  
  23. #include <iostream>
  24. #include <iomanip>
  25. using namespace std;
  26.  
  27. // Function prototype
  28. int binarySearch(const int array[], int size, int value);
  29.  
  30. int main()
  31. {
  32.     const int SIZE = 10;                     // Number of lottery tickets
  33.  
  34.     int tickets[SIZE] = {                    // Buyer's 10 "lucky" numbers (sorted)
  35.         13579, 26791, 26792, 33445, 55555,
  36.         62483, 77777, 79422, 85647, 93121
  37.     };
  38.  
  39.     int  winningNum;                         // This week's winning number
  40.     int  position;                           // Position returned by binary search
  41.  
  42.     // ----------------------------------------------------
  43.     // INPUT: Get this week's winning 5-digit number
  44.     // ----------------------------------------------------
  45.     cout << "Enter this week's winning 5-digit lottery number: ";
  46.     cin  >> winningNum;
  47.  
  48.     // Simple input validation for a 5-digit positive number
  49.     while (winningNum < 10000 || winningNum > 99999)
  50.     {
  51.         cout << "ERROR: Enter a VALID 5-digit number (10000 - 99999): ";
  52.         cin  >> winningNum;
  53.     }
  54.  
  55.     // ----------------------------------------------------
  56.     // PROCESSING: Binary search through the ticket list
  57.     // ----------------------------------------------------
  58.     position = binarySearch(tickets, SIZE, winningNum);
  59.  
  60.     cout << endl;
  61.     cout << fixed << setprecision(0);
  62.  
  63.     // ----------------------------------------------------
  64.     // OUTPUT: Report if any ticket is a winner
  65.     // ----------------------------------------------------
  66.     if (position != -1)
  67.         cout << "Congratulations! One of your tickets is a WINNER." << endl;
  68.     else
  69.         cout << "Sorry, none of your tickets is a winner this week." << endl;
  70.  
  71.     return 0;
  72. }
  73.  
  74. /********************************************************************************************
  75.  * BINARY SEARCH
  76.  * ------------------------------------------------------------------------------------------
  77.  * This function performs a binary search on a sorted integer array.
  78.  * It returns the index of the value if found, or -1 if the value is not in the array.
  79.  ********************************************************************************************/
  80. int binarySearch(const int array[], int size, int value)
  81. {
  82.     int first  = 0;              // First array index
  83.     int last   = size - 1;       // Last array index
  84.     int middle;                  // Midpoint index
  85.     int position = -1;           // Position of the value (if found)
  86.     bool found  = false;         // Flag to indicate if value is found
  87.  
  88.     while (!found && first <= last)
  89.     {
  90.         middle = (first + last) / 2;     // Calculate midpoint
  91.  
  92.         if (array[middle] == value)      // If value is found at middle
  93.         {
  94.             found = true;
  95.             position = middle;
  96.         }
  97.         else if (array[middle] > value)  // If value is in lower half
  98.         {
  99.             last = middle - 1;
  100.         }
  101.         else                             // If value is in upper half
  102.         {
  103.             first = middle + 1;
  104.         }
  105.     }
  106.  
  107.     return position;
  108. }
  109.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
13579
stdout
copy 
Enter this week's winning 5-digit lottery number: 
Congratulations! One of your tickets is a WINNER.
https://ideone.com/59otw3
language:
C++ (gcc 8.3)
created:
4 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!