//Ryan Shahriyarpour   CS1A  Chapter 8   Question 4
/*****************************************************************************
 * 
 * Charge Account Validation Modification
 * 
 *********************
 * 
 * This program lets the user enter a charge account number and determines
 * whether the number is valid by checking for it in a list of 18 valid
 * account numbers. It uses a BINARY SEARCH instead of a linear search.
 * 
 * *******************
 * A binary search only works on a sorted array, so the list is first
 * sorted with a SELECTION SORT. The binary search then checks the middle
 * element and throws away the half of the list that cannot hold the number,
 * repeating until the number is found or nothing is left to search.
 * 
 * INPUT
 *  account  - the charge account number to check
 * 
 * OUTPUT    
 *  A message saying whether the account number is valid or invalid
 * 
 ****************************************************************************/
 
#include <iostream>
using namespace std;
 
// Constant for the number of valid accounts
const int SIZE = 18;
 
// Function prototypes
void selectionSort(int array[], int size);
int binarySearch(const int array[], int size, int value);
 
int main()
{
    // data dictionary
    int accounts[SIZE] = {          // List of valid account numbers
        5658845, 4520125, 7895122, 8777541, 8451277, 1302850,
        8080152, 4562555, 5552012, 5050552, 7825877, 1250255,
        1005231, 6545231, 3852085, 7576651, 7881200, 4581002
    };
    int account;                    // Account number entered by the user
    int result;                     // Index where found, or -1 if not found
 
    // Sort the list so a binary search can be used
    selectionSort(accounts, SIZE);
 
    // Get the account number
    cout << "Enter a charge account number: ";
    cin >> account;
 
    // Binary search
    result = binarySearch(accounts, SIZE, account);
 
    // Display the result
    if (result == -1)
        cout << "\nThat account number is invalid." << endl;
    else
        cout << "\nThat account number is valid." << endl;
 
    return 0;
}
 
// Sorts the array into ascending order using a selection sort
void selectionSort(int array[], int size)
{
    // data dictionary
    int startScan;                  // Position being filled on this pass
    int index;                      // Loop counter that scans for the smallest
    int minIndex;                   // Index of the smallest value found
    int minValue;                   // The smallest value found
 
    for (startScan = 0; startScan < size - 1; startScan++)
    {
        minIndex = startScan;
        minValue = array[startScan];
        for (index = startScan + 1; index < size; index++)
        {
            if (array[index] < minValue)
            {
                minValue = array[index];
                minIndex = index;
            }
        }
        array[minIndex] = array[startScan];
        array[startScan] = minValue;
    }
}
 
// Returns the index of value in the sorted array, or -1 if not found
int binarySearch(const int array[], int size, int value)
{
    // data dictionary
    int first = 0;                  // First index still being searched
    int last = size - 1;            // Last index still being searched
    int middle;                     // Middle index of the range
    int position = -1;              // Index of the match (-1 = not found)
    bool found = false;             // True once the value is located
 
    while (!found && first <= last)
    {
        middle = (first + last) / 2;
        if (array[middle] == value)
        {
            found = true;
            position = middle;
        }
        else if (array[middle] > value)
            last = middle - 1;      // Value must be in the lower half
        else
            first = middle + 1;     // Value must be in the upper half
    }
    return position;
}