Hello! I have a question regarding the set up of my binary search. For my program I am working on, I have taken a .txt file full of first names and sent those first names to a string array. The names are then sorted, and from there I ask the user to input two first names of their choice. I would like to search for the two names the user inputs and let the user know how many times I found each specified first name. I then have the results sent to the last function, from which I display the results of the search. I have debugged the program and set everything up, but I fear that since I am sorta new to C++ that my format for the search could be set up better. Also I have set it up so that the first name is searched but I have not quite figured out how to get the second name or the results sent. For the results I mean whether or not the names were located and how many times the particular name was found.
Once again I appreciate all the help I have received, the way the help was offered was great. I was able to gather the knowledge and use the help to write the code in a matter that helped me understand it better.

I will attach the .txt files, my program files ect.....

Here is my header file:

// FILE: P1_NameSearch_Functions.h
// This program will cover strings, arrays, file I/O, pointers/references.
// OBJECTIVE: Read first names data & search for the corresponding user input. 

#include <string>				// Needed for string values

using namespace std;

/* This is the function that will be responsible for displaying the program's
   introduction, main objective, rules, and a brief user greeting. */
void Objective_screen(string *pName);

/* This is the function that will return a Boolean value, which is checked
   in main(). If the specified file can't be located, a message will be
   displayed to inform user, and the program with exit. If the file is found,
   the names[] array will be filled, and the total number of names that were
   read are returned to the main() function. */
bool ReadFile(string names[], int &rIndex);

/* This function uses a modified version of the 'bubble sort' to sort
   the names from the data file in a fashion that is requested. */
void bubbleSort(string names[], int &rIndex);

/* This function will use pointers and or references to obtain two names
   from the functions and then pass the specified names. */
void AskForTwoNames(string &rNameONE, string &rNameTWO);

/* The array, total number of names, and the user's specified selection 
   of two names is passed to this function (SearchNames()). Then it
   will pass the results (whether the names were found and how many
   times the names occurred). */
void SearchNames(string names[], int &rIndex, string &rNameONE, string &rNameTWO,
				 int &rCount_NameONE, int &rCount_NameTWO);

/* The WriteOutput() function takes the values (User Input) that was 
   passed to the function, and displays the results as well as outputs
   the results to the specified output file. The output file will
   serve as a brief summary for the user; if they desire to open it
   and read the information. */
bool WriteOutput(string *pName, string names[], int &rIndex, string &rNameONE, 
				 string &rNameTWO, int &rCount_NameONE, int &rCount_NameTWO);

Here is the functions:

// FILE: P1_NameSearch_Functions.cpp
// This program will cover strings, arrays, file I/O, pointers/references.
// OBJECTIVE: Read first names data & search for the corresponding user input. 

#include <iostream>				// Needed for cin and cout
#include <string>				// Needed for string values
#include <fstream>              // Reading/Writing file requires this standard library.
#include <string.h>

using namespace std;

// For easier access #define is used for file names
#define FILE_IN "FirstNames.txt"
#define FILE_OUT "FirstNames_Summary.txt"

void Objective_screen(string *pName)
	{
	// Declared variables
	char ENTER;

	// Greeting and introduction to the program
	// Ask for user name and return string
	cout << "\n     AUTHOR:		SELF EXPLANATORY ";
	cout << "\n     E-MAIL:		SELF EXPLANATORY ";
	cout << "\n      CLASS:		CIS 2275 ";
	cout << "\n ASSIGNMENT:		SELF EXPLANATORY \n";
	cout << "\n -------------------------------------------------------------- ";
	cout << "\n       C++ U.S. CENSUS DATA MOST COMMON FIRST NAME SEARCH ";
	cout << "\n -------------------------------------------------------------- ";

	cout << "\n                  HELLO!                      ";
	cout << "\n My name is Page, and I will go over the main "
		 << "\n objective and instructions for my program. \n";
	cout << "\n If you do not mind, I have a question...";
	cout << "\n What is your full name? ";
	getline(cin, *pName);
	
	cout << "\n Nice to meet you " << *pName << ". \n";
	cout << "\n This program will make use of input/output files for the "
		 << "\n census data. This program will search the census data for "
		 << "\n user specified occurences of popular first names. ";
	cout << "\n This program will visually narrate the steps that this "
		 << "\n program goes through to achieve the final results. \n";

	cout << "\n TO START THE PROGRAM HIT THE ENTER TO BEGIN... \n";
	// Waits for user's input before program continues
	cin.get(ENTER);
}

bool ReadFile(string names[], int &rIndex)
{
	/* This is the function that will fill the names[] array,
	   after the data file has been successfully located.*/

	// Declared Variables
	string filename = "FirstNames.txt";
	
	/* Uses the 'open' member function of the ifstream object to
	   open a file for reading/input. */
	ifstream FirstNamesInput;

	/* Since the file name is a string the 'open' element needs a char[].
	   So, it is nessecary to us the c_str() function to give the string
	   in proper char[] format. */
	FirstNamesInput.open(filename.c_str()); 

    // Here we must make sure that the file was opened
	if(!FirstNamesInput)
	{
		cout << "\n		Opps! Error... Cannot Locate \"" << FILE_IN << "\"";
		cout << "\n ----------------------------------------------------- \n " << endl;
		exit(1);
		// Returns the false value (or failure) in boolean form
		return false;
	}
	
	/* Needed to make sure I count the words/names in the .txt file.
	   The &rIndex is used as a reference parameter to located the
	   total number of strings in the file as well as the first element. */
		rIndex = 0;
        
		while(FirstNamesInput >> names[rIndex])
        ++rIndex;
		cout << "\n There are a total of " << rIndex << " names in the file. " << endl;
	
		// Collecting data for the array and filling the names into the array.
	
		// Returns the true value (or success) in boolean form
		return true;
}

void bubbleSort(string names[], int &rIndex)
{
	// Declared Variables
	// This is used for a place holder of a temporary string (name).
	string temp;

	/* This loop compares the availible adjacent values, and moves the values around
	   untill they are in the correct order. In other word... it will help to properly
	   sort the names in this situation. */
	
	// This is the first of dual (nested) loops
	for(int i = 0; i < rIndex - 1; ++i)							
	{
		bool swapped = false;
		
		// This is the second of dual (nested) loop
		for(int j = 1; j < rIndex; ++j)							
		{
			/* This is used to determine if the specified array 
			   element [j - 1] is larger than [j]. */
			if(names[j - 1] > names[j])
			{
				// Temp holds value of [j - 1]
				temp = names[j - 1];							
				// Array element is assigned the value of [j - 1]
				names[j - 1] = names[j];						
				// Element [j - 1] is replaced by temp
				names[j] = temp;								
			}
		}
	}
}
 
void AskForTwoNames(string &rNameONE, string &rNameTWO)
{
	// This function will ask the user to input two first names of thier choice.
	cout << "\n Enter in two first names, in CAPS, seperated by a space:      ";
	cin  >> rNameONE >> rNameTWO;
	
	// This was to be used if I had to collect both names into one variable.
    // int index = rUserInput.find(" ");
    // rNameONE = rUserInput.substr(0,index-1);
    // rNameTWO = rUserInput.substr(index+1);
}

void SearchNames(string names[], int &rIndex, string &rNameONE, string &rNameTWO, 
				 int &rCount_NameONE, int &rCount_NameTWO)
{

	/* This is a standard Binary Search Alogorithm, slightly modified to be more
	   efficient with my particular assingment. This search takes a sorted array
	   of values, names, or character and takes the total amount or Index. Then
	   the total amount of items is saved, and the high and low values are added
	   and divided by 2. This value will be the middle and so fourth the idea. */
	
	// Basic Binary Search Alogorithm

	/********** Declared Variables **********/

	// When ever low and high cross the process has ended
	// HigherBound will begin by equaling the last index.
	int HigherBound = rIndex - 1;
	// LowerBound will begin in the very front of the Array
	int LowerBound = 0;
	// This will hold the average of High and Low
	int MiddleBound = 0;
	// Use as a simple boolean
	int Found = 0;
	// This will hold how many time we have looped
	int Permutation = 0;

	// Initialize Counter
	rCount_NameONE = 0;
	rCount_NameTWO = 0;
	
	// Start of Binary Search
	while ((LowerBound <= HigherBound) && (Found == 0))
	{
		MiddleBound = (LowerBound + HigherBound) / 2;			
		
		if(names[MiddleBound] == rNameONE)
		{
			Found = 1;
			++rCount_NameONE;
		}
		else if(names[MiddleBound] < rNameONE)
		{
			LowerBound = MiddleBound + 1;
		}
		else
		{
			HigherBound = MiddleBound - 1;
		}

	 // View whats going on in this loop    
	 // This is just temporary to see if successfull
	 // If works properly I will send results to WriteOutput(); function.
	 cout << "\n             The Search Was Run: " << Permutation << " Times. ";
	 cout << "\n The Index's Higher-Bound Value: " << HigherBound;
	 cout << "\n The Index's Middle-Bound Value: " << MiddleBound;
	 cout << "\n  The Index's Lower-Bound Value: " << LowerBound << endl;
	 // This value holds the amount of loops (How many cycles)
	 Permutation++;						
	}
	if(Found == 1)
	{
		cout << rNameONE << " Is In The List, " << rCount_NameONE << " Times. ";
		cin.get();
	}
	else 
	{
		cout << rNameONE << " Is Not In The List. ";
		cin.get();
	}										
		cin.get();
}										

bool WriteOutput(string *pName, string names[], int &rIndex, string &rNameONE, 
				 string &rNameTWO, int &rCount_NameONE, int &rCount_NameTWO)
{
	/* The WriteOutput() function recieves the values that were passed to them
	   as well as the users input for the search and displays them to the
	   screen. This file also shows the user the output file for the results
	   and or summary of the outcome of the program. */
	
	// Declared Variables
	string filename = "FirstNames_Summary.txt";
	
	// This will make FirstNamesOutput cast as cin or cout
	ofstream FirstNamesOutput;										
	// Needed to open output file
	FirstNamesOutput.open(filename.c_str());								

	// This is used to test if the specified output file exists
	if(!FirstNamesOutput)
	{
		// Let user know if there was an error and/or no output file was found
		cout << "\n		Opps! Error... Cannot Locate \"" << FILE_OUT << "\"";
		cout << "\n ----------------------------------------------------- \n " << endl;
		exit(1);
		
		// Returns the false value (or failure) in boolean form
		return false;
	}
	else
	{
		// Let user know that the program has successfully found and identified output file
		cout << "\n CONGRATULATIONS! ";
		cout << "\n THE C++ U.S. CENSUS DATA MOST COMMON FIRST NAME SEARCH "
			 << "\n Has Located The Data Output File! ";
	
		FirstNamesOutput << "\n         AUTHOR:		SELF EXPLANATORY ";
		FirstNamesOutput << "\n          CLASS:		CIS 2275 ";
		FirstNamesOutput << "\n     ASSIGNMENT:		SELF EXPLANATORY \n";
		FirstNamesOutput << "\n -------------------------------------------------------------- ";
		FirstNamesOutput << "\n       C++ U.S. CENSUS DATA MOST COMMON FIRST NAME SEARCH ";
		FirstNamesOutput << "\n -------------------------------------------------------------- \n";
		FirstNamesOutput << "\n ------------RESULTS------------ \n";
		FirstNamesOutput << "\n    USER'S NAME:	    " << *pName;	
		FirstNamesOutput << "\n   USER'S INPUT:		" << rNameONE << "    " << rNameTWO;  
		FirstNamesOutput << "\n SEARCH OUTCOME:     ";
	}

	cout << "\n To view program outcome/results open the following: \"" << FILE_OUT << "\"";

	// Reading and writing complete, closing file.
	FirstNamesOutput.close();
	
	return true;
}
// END OF C++ U.S. CENSUS DATA MOST COMMON FIRST NAME SEARCH

Here is the driver:

// FILE: P1_NameSearch_Driver.cpp
// This program will cover strings, arrays, file I/O, pointers/references.
// OBJECTIVE: Read first names data & search for the corresponding user input. 

#include <iostream>				// Needed for cin and cout
#include <string>				// Needed for string values
#include <fstream>              // Reading/Writing file requires this standard library.

using namespace std;

#include "P1_NameSearch_Functions.h"

int main()
{
	// Declared Variables
		string names[800], pName, rNameONE, rNameTWO, answer;
		int rIndex, rCount_NameONE, rCount_NameTWO;
	
		// Function for the Objective Screen
		Objective_screen(&pName);

		cout << "\n Data Contained In \"FirstNames.txt\" \n";
	do {
		
		// Call ReadFile() function to read data (names) into names[];
		// The ReadFile() function will return a false if the file can't be found.
		if(!ReadFile(names, rIndex))
			
		/* This calls the bubbleSort() function from where the array names[]
		   is read and sorted via its values. */
		bubbleSort(names, rIndex);

		/* The function called AskForTwoNames() will use pointer and or 
		   references to obtain two names from the functions. */
		AskForTwoNames(rNameONE, rNameTWO);

		
		SearchNames(names, rIndex, rNameONE, rNameTWO, rCount_NameONE, 
								 rCount_NameTWO);
		
		bool ok = WriteOutput(&pName, names, rIndex, rNameONE, rNameTWO,
								  rCount_NameONE, rCount_NameTWO);
		
		// Ask the user if they would like to search names again.
		cout << "\n Would you like to search again? "
			 << "\n Please type answer in CAPS! (YES or NO)? ";
		cout << "\n Please hit the enter key twice! \n\n";
		getline(cin, answer);
		
		}while (answer == "YES");

		return 0;
}

I will attach the .txt file that contains the names, but I will leave out the "summary file", it is basically self explanatory.

Thank you,


Page

Are you supposed to use your own data structure or can you use std::map?
The way I see it using map would be the easiest approach.
Of course if you have "huge" number of names, map may not be optimal (from memory pov).

Are you supposed to use your own data structure or can you use std::map?
The way I see it using map would be the easiest approach.
Of course if you have "huge" number of names, map may not be optimal (from memory pov).

Well, I can, but the main focus of the program is to be a 'tenative' review of; strings, arrays, file I/O, pointers/references. Would you elaborate on both? I am curious of the way you would implement using a map. From what I have gathered so far, I was told that for large amounts of data (for example: There is a total of 732 names) that it is easiest to use binary (or basically just cutting the index in half and using high, low, and middle searching) for large amounts. But I have just recently learned how binary search algorithms work. I wouldn't mind learning other methods of searching.

I have a question:
If I want to search for both names consecutively would this code work to find them? Or am I totally wrong? If so can you point me in the correct direction and let me know what I did wrong.

void SearchNames(string names[], int &rIndex, string &rNameONE, string &rNameTWO, 
				 int &rCount_NameONE, int &rCount_NameTWO)
{

	/* This is a standard Binary Search Alogorithm, slightly modified to be more
	   efficient with my particular assingment. This search takes a sorted array
	   of values, names, or character and takes the total amount or Index. Then
	   the total amount of items is saved, and the high and low values are added
	   and divided by 2. This value will be the middle and so fourth the idea. */
	
	// Basic Binary Search Alogorithm

	/********** Declared Variables **********/

	// When ever low and high cross the process has ended
	// HigherBound will begin by equaling the last index.
	int HigherBound = rIndex - 1;
	// LowerBound will begin in the very front of the Array
	int LowerBound = 0;
	// This will hold the average of High and Low
	int MiddleBound = 0;
	// This will hold how many time we have looped
	int Permutation = 0;
	// Use as a simple boolean
	int Found_rNameONE = 0;
	int Found_rNameTWO = 0;

	// Initialize Counter
	rCount_NameONE = 0;
	rCount_NameTWO = 0;
	
	// Start of Binary Search to find rNameONE & rNameTWO
	while ((LowerBound <= HigherBound && Found_rNameONE == 0) || (LowerBound <= HigherBound && Found_rNameTWO == 0))
	{
		MiddleBound = (LowerBound + HigherBound) / 2;			
		
		if((names[MiddleBound] == rNameONE) || (names[MiddleBound] == rNameTWO))
		{
			Found_rNameONE = 1;
			Found_rNameTWO = 1;
			++rCount_NameONE;
			++rCount_NameTWO;
		}
		else if((names[MiddleBound] < rNameONE) || (names[MiddleBound] < rNameTWO))
		{
			LowerBound = MiddleBound + 1;
		}
		else
		{
			HigherBound = MiddleBound - 1;
		}
		// This value holds the amount of loops (How many cycles)
		Permutation++;	
	}
	if(Found_rNameONE == 1 || Found_rNameTWO == 1)
	{
		cout << rNameONE << " Is In The List, " << rCount_NameONE << " Times. ";
		cout << rNameTWO << " Is In The List, " << rCount_NameTWO << " Times. ";
		cin.get();
	}
	else 
	{
		cout << rNameONE << " Is Not In The List. ";
		cout << rNameTWO << " Is Not In The List. ";
		cin.get();
	}										
		cin.get();		
}

I'm a bit confused about the multimap aspect. OP has a list of names, there's no real pairings (there just happens to be two names to search for). There are certainly more diverse search options available but I wouldn't change data structures completely unless you know it will save more time than you've already spent.
The search seems to work if there's just one instance of either of the names. The best way to cover multiple instances, I think (someone will probably have a more effective idea) is when you find a name, march backwards from the MiddleBound through the list until you don't find it anymore, then go back to the MiddleBound and go forward until you don't find it anymore (so effectively 2 while loops or 1 if you want to skip over middlebound while you're iterating). You get the idea. See if that works, if it does you're all set but if it doesn't you may have to rework your if statements in the search function and run it one name at a time.

Ok, so its my while loop that needs to be re-worked. I knew there was a logic problem but I just wasn't sure If I was doing it right. But I will try to implement two. I would use the multimap but I just don't really understand it all that much. I would like to learn about it but I don't think I should implement it if I don't fully understand it.
But I would like to thank you both for your inputs, I appreciate it.

I am having another problem, I can't even get the loop to find one name.

void SearchNames(string names[], int &rIndex, string &rNameONE, string &rNameTWO, 
				 int &rCount_NameONE, int &rCount_NameTWO)
{

	/* This is a standard Binary Search Alogorithm, slightly modified to be more
	   efficient with my particular assingment. This search takes a sorted array
	   of values, names, or character and takes the total amount or Index. Then
	   the total amount of items is saved, and the high and low values are added
	   and divided by 2. This value will be the middle and so fourth the idea. */
	
	// Basic Binary Search Alogorithm

	/********** Declared Variables **********/

	// When ever low and high cross the process has ended
	// HigherBound will begin by equaling the last index.
	int HigherBound = rIndex - 1;
	// LowerBound will begin in the very front of the Array
	int LowerBound = 0;
	// This will hold the average of High and Low
	int MiddleBound = 0;
	// This will hold how many time we have looped
	int Permutation = 0;
	// Use as a simple boolean
	int Found_rNameONE = 0;
	int Found_rNameTWO = 0;

	// Initialize Counter
	rCount_NameONE = 0;
	rCount_NameTWO = 0;
	
	
	// Start of Binary Search
	// Start of Binary Search to find rNameONE
	while (LowerBound <= HigherBound && Found_rNameONE == 0)
	{
		MiddleBound = (LowerBound + HigherBound) / 2;			
		
		if(names[MiddleBound] == rNameONE)  
		{
			Found_rNameONE = 1;
			++rCount_NameONE;
		}
		else if(names[MiddleBound] < rNameONE)  
		{
			LowerBound = MiddleBound + 1;
		}
		else
		{
			HigherBound = MiddleBound - 1;
		}
		
		// This value holds the amount of loops (How many cycles)
		Permutation++;	
	}
	if(Found_rNameONE == 1)
	{
		cout << rNameONE << " Is In The List, " << rCount_NameONE << " Times. ";
	}
	else 
	{
		cout << rNameONE << " Is Not In The List. ";
	}	

	
}

You have names[MiddleBound] < rNameONE but what happens if the opposite is true? How do the boundaries shift?

Rather than coding the method for rNameONE and another exactly the same for rNameTWO why not have a method that takes in a name and a count for that name, both by reference (index and names too) . Then you can call the method twice from your main(). That way if you want to expand the search to 3 names you have the flexibility.

Can anyone show me what I am doing wrong? I just can't understand the wiki site or any of the other ones I have been shown. The examples are not clear and I am really really confused!

void SearchNames(string names[], int &rIndex,string &rName,int &rCount_Name)
{

	
	// Basic Binary Search Alogorithm

	/********** Declared Variables **********/

	//all the variables you had here

	
	// Start of Binary Search to find rName & rName
	while ((LowerBound <= HigherBound && Found_rName == 0))
	{
		MiddleBound = (LowerBound + HigherBound) / 2;			
		
		if(names[MiddleBound] == rName)
		{
			Found_rName = 1;
			
			++rCount_Name;
								
		}	


		else if(names[MiddleBound] < rName)
		{
			LowerBound = MiddleBound + 1;
		}
		else
		{
			HigherBound = MiddleBound - 1;
		}
		// This value holds the amount of loops (How many cycles)
		Permutation++;	
	}
	if(Found_rName == 1)
	{
		cout << rName << " Is In The List, " << rCount_Name << " Times. "<<endl;
				
	}
	else 
	{
		cout << rName << " Is Not In The List. "<<endl;
	}										
			
}

I whittled away some things, the search only does one at a time. I think doing both was seriously goofing things up and would turn out to probably be inefficient by pushing your middle point all over the list.

call it in main like: SearchNames(names, rIndex, rName1,rCount_Name); you'll have to swap some of those variable names around.

I also took out the cin.get()s that were inside of the method, since the return to main after the method completes won't clear the screen. You can leave one at the end of main().

Just a suggestion, how about first primarily focusing on coding well-working basic routines (i.e. sorting, searching in this case), without them being 'slightly modified' for any specific purpose. Hence you would have something solid to further build upon.

In other words, you would have a sorted array of strings, and you'd be able to issue a simple search telling you if a string is in the array, and if so, where it is. Hence the next problem to solve would be to try to figure out how many occurrences of the string there are. (It seems like your attempt to be efficient here is what leads to the confusion.)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.