Binary Search

[stoneJax]

#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;

void initialize(/*inout*/int[], /*in*/int);                  // List of function prototypes.
void getTestScores(/*inout*/int[], /*in*/int);
void fileInput(/*inout*/int[], /*in*/int);
int showScores(/*in*/const int[], /*in*/int);
int highest(/*in*/const int[], /*in*/int);
int getLowest(/*in*/const int[], /*in*/int);
double average(/*in*/const int[], /*in*/int);
void getScore(/*in*/const int[], /*in*/int);
void selectionSortAs(int[], int);
void selectionSortDe(int[], int);
void binarySearch(const int[], int);


int main()
{
    const int SIZE = 10;                                // Array size
    int testScores[SIZE];                               // Array of test scores
    int choice = 0;                                     // Needed for menu interface

    initialize(testScores, SIZE);                       // Function call to initialize the array testScores()
                                                        // each of ten elements to zero.
    do                                                  // Display menu as long as user doesn't type 11 to quit.
    {
        cout << endl;
        cout << " 1. Read in 10 scores (integers) from the user." << endl;
        cout << " 2. Read in 10 scores from a file, scores.txt." << endl;
        cout << " 3. Print the 10 scores." << endl;
        cout << " 4. Print the highest score." << endl;
        cout << " 5. Print the lowest score." << endl;
        cout << " 6. Print the mean (average) of the 10 scores." << endl;
        cout << " 7. Print a score based on an entry or row# and show how many scores are higher." << endl;
        cout << " 8. Sort scores (acsending sort)." << endl;
        cout << " 9. Sort scores (decsending sort)." << endl;
        cout << "10. Search for a score." << endl;
        cout << "11. Exit the program." << endl << endl;
        // Prompt user for an option
        cout << "Enter an option such as 1 or 2 etc: ";              // Get user's choice.
        cin >> choice;

        switch(choice)                                               // Access the correct function to handle
        {                                                            // user's choice.
            case 1:  getTestScores(testScores, SIZE);
                break;
            case 2: fileInput(testScores, SIZE);
                break;
            case 3: showScores(testScores, SIZE);
                break;
            case 4: highest(testScores, SIZE);
                    cout << "The highest number is " << highest(testScores, SIZE) << endl;
                break;
            case 5: cout << "The lowest score is " << getLowest(testScores, SIZE) << endl;
                break;
            case 6: cout << "The average score is " << average(testScores, SIZE) << endl;
                break;
            case 7: getScore(testScores, SIZE); // Show test score from the array given a number.
                break;
            case 8: selectionSortAs(testScores, SIZE);
                break;
            case 9: selectionSortDe(testScores, SIZE);
                break;
            case 10: binarySearch(testScores, SIZE);
                break;
            case 11: cout << "Come back to access your data later.";
                break;
            default: cout << "INVALID INPUT." << endl;
        }

    } while (choice != 11);

    return 0;
}



//***********************************************************************************
// Function will initialize all the elements of an aray to zero.
// Pre: Array testScores[] sent in from main with a size of ten.
// Post: Each element is initialized to zero and zent back to main.
void initialize(/*inout*/int scores[], /*in*/int size)
{
    for(int count = 0; count <= size; count++) // Initialize array element to zero.
        scores[count] = 0;
}
//***********************************************************************************





//*********************************************************************************************************
// The getTestScores function accepts an array and its size as arguments. It prompts the user to enter test
// scores,  as arguments. It prompts the user to enter test scores, which are stored in the array.
// Pre: An integer array has been declared in the calling function with a known size.
// Post: Array's elements are filled with user input and sent back to main
void getTestScores(/*inout*/int scores[], /*in*/int size)
{
   for(int count = 0; count <= size - 1; count++)
   {
      cout << "Enter test score number " << (count + 1) << ": ";           // Get each test score.
      cin >> scores[count];
   }
}
//*********************************************************************************************************






//*****************************************************************************************
// Function will allow user to input a file consisting of numbers to be used in the program
// Pre: Array testScores[] is sent in from main with a size of ten elements.
// Post: Array elements are filled with numbers from file and sent back to main.
void fileInput(/*inout*/int testScores[], /*in*/int size)
{
    string fileName;
    ifstream inData;

    cout << "Enter a filename: ";
    cin >> fileName;
    inData.open(fileName.c_str());

    for (int count = 0; count < size; count++)
        inData >> testScores[count];

}
//******************************************************************************************






//******************************************************************************************************
// Function Will display the values stored in each element of the array with a consequtive numbered list.
// Pre: An integer array has been declared in the calling function with a known size.
// Post: Algorithm will display contents, one per line.
int showScores(/*in*/const int scores[], /*in*/int size)
{
    for(int count = 0; count <= size; count++)
    {
        if((count + 1) == size)              // Prints one less whitespace for row #10. Keeps numbers aligned.
        {
            cout << "score #" << count + 1 << ":      " << scores[count] << endl;
            return 0;
        }
        cout << "score #" << count + 1 << ":       " << scores[count] << endl; // Prints rows one through nine.
    }
}






//****************************************************
// The getLowest function accepts a double array and *
// its size as arguments. The lowest value in the    *
// array is returned as a double.                    *
//****************************************************

int getLowest(/*in*/int const scores[], /*in*/int size)
{
   int lowest;  // To hold the lowest value

   // Get the scores first array element.
   lowest = scores[0];

   // Step through the rest of the array. When a
   // value less than lowest is found, assign it
   // to lowest.
   for (int count = 1; count < size; count++)
   {
      if (scores[count] < lowest)
         lowest = scores[count];
   }
   return lowest;
}




double average(/*in*/const int testScores[], /*in*/int size)
{
    int sum = 0;
    double average = 0;
    for (int count = 0; count < size; count++)
    {
        sum = sum + testScores[count];
    }
    average = sum / 10.00;
    return  average;
}



void getScore(/*in*/const int scores[], /*in*/int size)
{
    int row = 0, score = 0, higher = 0;

    cout << "Please enter entry or row # of score you want: ";
    cin >> row;

    while(row < 0 || row > size - 1)
    {
        cout << "Invalid row, Please enter entry or row # of score you want: ";
        cin >> row;
    }
    score = scores[row - 1];
    cout << "Entry # " << row << " score: " << score << endl;

    higher = score;
    for (int count = 0; count < size; count++)
    {
        if(scores[count] > higher)
            higher = scores[count];
    }
    cout << "Score statistics: " << higher << " higher" << endl;
}

[Handy Andy]

Hello stoneJax,

While I look at your program hav a look at these links:

PLEASE ALWAYS USE CODE TAGS (the <> formatting button), to the right of this box, when posting code.

It makes it easier to read your code and also easier to respond to your post.

http://www.cplusplus.com/articles/jEywvCM9/
http://www.cplusplus.com/articles/z13hAqkS/

Hint: You can edit your post, highlight your code and press the <> formatting button.
You can use the preview button at the bottom to see how it looks.

I found the second link to be the most help.

Also if you could post your input file, or a good sample if large, it would help everyone working with this program to be able to use the same information that you do.

Andy

[Handy Andy]

Hello stoneJax,

What happened to the function "fileInput()"? You have the prototype and function call, but no function definition.

Also missing "highest" and "getLowest" functions.

Andy

Edit:

[stoneJax]

Thank you for the info on formatting the code; definitely easier to look at. I have re-posted my code above and the rest of it here since there is a word limit. Also, I have done a little more work on it and now I only get the "stack smashing" notice when choosing option 11 to quit (this has only come along after adding the binary search function). In addition, there are a couple other things that I am trying to fix complete the program. In case 7 there is a function call to getScore() where the function does not read the value stored at row #10 (it reads all values before that), and I am trying to figure out how to get this function to count how many numbers in the array are higher than the one selected. Finally, the binary search function does not work after re-organizing numbers with the descending selection sort function, but it does work otherwise.

As for the list of numbers that I am working with, I select option 1 from the menu and type 1,2,3,4,5,6,7,8,9,0.

Note: If you run the program and re-organize the array, or want to display the contents of the array, then choose option 3 from the menu.

//********************************************************************
// The selectionSort function sorts an int array in ascending order. *
//********************************************************************
void selectionSortAs(int array[], int size)
{
   int minIndex, minValue;

   for (int start = 0; start < (size - 1); start++)
   {
      minIndex = start;
      minValue = array[start];
      for (int index = start + 1; index < size; index++)
      {
         if (array[index] < minValue)
         {
            minValue = array[index];
            minIndex = index;
         }
      }
      array[minIndex] = array[start];
      array[start] = minValue;
   }
}





//********************************************************************
// The selectionSort function sorts an int array in decending order. *
//********************************************************************
void selectionSortDe(int array[], int size)
{
   int minIndex, minValue;

   for (int start = 0; start < (size - 1); start++)
   {
      minIndex = start;
      minValue = array[start];
      for (int index = start + 1; index < size; index++)
      {
         if (array[index] > minValue)
         {
            minValue = array[index];
            minIndex = index;
         }
      }
      array[minIndex] = array[start];
      array[start] = minValue;
   }
}



void binarySearch(const int array[], int size)
{
    int first = 0,             // First array element
       last = size - 1,       // Last array element
       middle, value,               // Mid point of search
       position = -1;         // Position of search value
    bool found = false;        // Flag

    // Get a value to search for.
    cout << "Enter the value you wish to search for: ";
    cin >> value;

    while (!found && first <= last)
   {
      middle = (first + last) / 2;     // Calculate mid point
      if (array[middle] == value)      // If value is found at mid
      {
         found = true;
         position = middle;
      }
      else if (array[middle] > value)  // If value is in lower half
         last = middle - 1;
      else
         first = middle + 1;           // If value is in upper half
   }

    // If position contains -1 the value was not found.
    if (position == -1)
        cout << "That number does not exist in the array.\n";
    else
    {
    // Otherwise position contains the subscript of
    // the specified employee value in the array.
    cout << "The value " << value <<  " is found at element " << position << " in the array.\n" << endl;
    }
}

[Handy Andy]

Hello stoneJax,

Earlier I tested "selectionSortAs" and "selectionSortDe" and they both worked fine.

Today I tested, the original, "binarySearch()" and it worked, but only on an array that was sorted in ascending order. My suggestion would be to call "selectionSortAs" before you do the binary search.

In the "showScores" function I adjusted the "cout" statement to:

cout << std::setw(8) << "score #" << std::setw(2) << count + 1 << ": " << std::setw(3) << scores[count] << endl;

IMHO I think it looks better.

In the "average" function I adjusted the line above the return to: average = static_cast<double>(sum) / size; This way it prints a true average not something close, i.e., an int representation of a "double", which is just the whole number.

That just leaves the highest and lowest functions.

Hope that helps,

Andy

[stoneJax]

Thank for taking the time to look through.

I am in my first semester of C++ and I am not yet familiar with "std::." However when I tried it it printed out an extra row for number 11 with a value of zero. I do not understand why since the array only has ten values. With the code that I already have in place before trying the suggestion it will print 10 rows which is what matches the values entered into the array.

The functions for highest and lowest are working.

Any suggestions on how to find how many numbers in the array are higher than the selected number. It is in the last part of the getScore() function. This is what I tried working with but I know it's wrong.

 higher = score;
    for (int count = 0; count < size; count++)
    {
        if(scores[count] > higher)
            higher = scores[count];
    }
    cout << "Score statistics: " << higher << " higher" << endl;

[Handy Andy]

Hello stoneJax,

"std::" is what you have to use when you do not use the line using namespace std;. Since I do not use this line I have to qualify what is in the standard namespace. Using "std::cout" in the "showScores" function has nothing to do with printing an extra line.

I did notice two things.:

First you edited your OP (original post) and I am not sure what you added except maybe the "fileInput" function. Since I put this function at the end of my file and they are different I believe it was not there from the beginning. Or I could be wrong. PLEASE do not edit, add to or change the OP as it is confusing to people. Just put the changes in another message.

Second in "showScores" the for loop is working on "i <= size". This will give the subscript a value of zero to 10 putting you one outside the boundary of the array. This is undefined behavior and you are just lucky that it prints a zero. Change "<=" to just "<" and it should solve your problem.

For your bit of code, using what you started with I came up with this:

for (size_t lc = 0; lc < size; lc++)
{
	if (scores[lc] > scores[row - 1])
		higher++;
}

The type "size_t" can simply be thought of as another name for "unsigned int". In my VS 2017 it will give me a template of sorts as for (size_t lc = 0; lc < length; lc++). I changed the "i" to "lc" because that is what I am use to working with. The "size_t" is used because there are several functions that you can use in place of "length" that return a "size_t" variable.

This worked when I ran the program.

Lastly when reading a file like you do this is more likely to work better than the for loop that you have:

void fileInput(int testScores[], const size_t SIZE)
{
	size_t i{};
	std::string inFileName{ "scores.txt" };

	std::ifstream inFile(inFileName);

	if (!inFile)
	{
		std::cout << "\n File " << inFileName << " did not open" << std::endl;
		std::this_thread::sleep_for(std::chrono::seconds(3));  // <--- Needs header files chrono" and "thread".
		exit(1);
	}

	while (inFile >> testScores[i] && i < SIZE)
		i++;
}

The while loop will read what is in the file and up to a maximum of ten scores. Should the while loop read less than ten scores the value of "i" can be returned to main and sent to other functions to use in for loops that will only use the part of the array that was filled. Thus instead of calling other functions sending it "SIZE" (defined as ten) you use the variable that holds the actual number read from the file.

Hope that helps,

Andy

[stoneJax]

Hi Andy,

Sorry for re-placing the old post with the new one; I'll remember to make an additional post for future reference.

For the showScores() function I modified "for(int count = 0; count < size; count++)"
to "for(int count = 0; count < size; count++)" leaving out the = sign like you said. Now I can use a single cout statement with the field width manipulators to get exactly ten rows to match the ten array elements. I modified the cout statement slightly so it now looks like:
cout << setw(8) << "score #" << setw(2) << count + 1 << ": " << left << setw(3) << scores[count] << endl;
I added the left alignment and omitted the std:: simply because that has not been introduced in my class. Is there any added benefit that allows the programmer more control with std:: ?

I appreciate the knowledge you extended about using size_t in the fileInput() function. That seems a lot more practical in real life to have an array that may not potentially fill all it's elements. Arrays are just being introduced in class and they are giving the array a fixed size. However, I care more about learning rather than just passing assignments, so the info is interesting.

[stoneJax]

Update for the getScore() function. I figured out a correct code for counting the number of scores that are higher than the user's selected choice.

int countNumberOfHigherScores = 0;

for (int count = 0; count < size; count++)
    {
        if(scores[count] > score)
            countNumberOfHigherScores++;
    }
    cout << "Score statistics: " <<  countNumberOfHigherScores << " higher" << endl;

All my functions seem to be pretty solid now, except for the binarySearch() function.
This function will not read the ninth element in the array (but it does read 0-8). Also, if the array is arraigned in descending order then the binarySearch() does not work.

Outside of this the only problem I see is when selecting #11 from the menu to quit, the corresponding case 11 in the switch will not print out the cout statement. Instead the program crashes and displays the stack smashing report in the terminal.

[Handy Andy]

Hello stoneJax,

Is there any added benefit that allows the programmer more control with std:: ?

The only benefit of using "std::" is the using WILL be a problem some day. When you put using namespace std; in the global scope of the program the compiler will try to put "std::" in front of your variables and function calls. Normally this is not a problem until a variable name or function that you write happens to have the same name as what is in the standard name space then the compiler will use what is in the standard name space or generate an error because what you are doing is not what is expected from what is in the standard name space.

Something that you could use in place of "using namespace std;" is:

using std::cout;
using std::cin;
using std::endl;
using std::string;

This will limit what you are using and be less of a problem.

I hope by the end of this class or the beginning of the next class you learn more about name spaces and how to use them.

In the line:
cout << setw(8) << "score #" << setw(2) << count + 1 << ": " << left << setw(3) << scores[count] << endl;
I would have thought that you would have put "left" at the beginning of the line nor before the numbers. Numbers tend to work better "right' justified especially with a decimal number. It lines up the decimal point better. If you like the output this way this is fine.

You will learn that there are many parts in C++ that use an "unsigned int" and typing "size_t" is a bit easier. Also something like "stringName.size()" is defined as size_type size() const; and under the section of "Return Value" it says Member type size_type is an unsigned integral type. Which basically says that size_type is the same as size_t.

As you have found out the "binary search" only works with an array in ascending order. You might be able to make it work with an array in descending order, but you would have to know which order the array is in before calling the function or write an overloaded function to use the descending order.

I do not recall having any problem with choice 11, but I will check it out along with the search problem.

I just tested case 11 with your new code and did not have any problem, but I would suggest this:
cout << "\n Come back to access your data later.";

Hope that helps,

Andy

[stoneJax]

I noticed having having "left" where I put it caused the alignment of the first line to be off a little. I tried it in the beginning like you said and now it works perfectly.

I was assuming the binary search function should work in both ascending and descending, but now I understand that it's only supposed to work in descending.

Interesting that you did not have any problems with case 11. My program crashed every time; I'm using Code Blocks on a 2010 Mac Book Pro running Ubuntu 18.04 (IDK if that makes a difference). I talked to my instructor about it and he wasn't positive what the issue was, but said something may be conflicting with having an exit case and a default case. His solution was to add the #include <cstdlib> header and place an exit function "exit(0)" at the end of case 11 and now cout statement is printed and the program properly closes.

Thank you for all your help and the extra information!