help with Binary Search

[scu1casper]

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <algorithm>
using namespace std;

// global constants
const int MAX_CUSTOMERS = 1000;
int maxStringSize = 8;
int maxTempSize = 3;
const int NOT_FOUND = -1;

// function prototypes
bool OpenAndValidateInputFile (ifstream& textIn);
void ReadAndStoreInputFile (ifstream& textIn, string Customer[], double Charge[], int& counter);
void SelectionSort (string Customer[], double Charge [], int counter);
bool OpenAndValidateOutputFile (ofstream& textOut);
void WriteToOutputFile (ofstream& textOut, string Customer [], double Charge [], int counter);
void DisplayChargesForCustomers (ofstream& textOut, int counter, string Customer [], string userCustomerCode);
bool GetUserInput (string &userCustomerCode);
void ValidateCustomerCode (string& userCustomerCode, int counter, string Customer []);
void BinarySearchForCustomerCode (string userCustomerCode, int counter, string Customer []);

int main()
{
	// local variables
	ifstream textIn;														// input file stream variable
	ofstream textOut;
	string Customer [MAX_CUSTOMERS];
	double Charge [MAX_CUSTOMERS];
	int counter = 0;
	string userCustomerCode;

	if (OpenAndValidateInputFile (textIn))
	{
		ReadAndStoreInputFile (textIn, Customer, Charge, counter);

		SelectionSort (Customer, Charge, counter);

		if (OpenAndValidateOutputFile (textOut))
		{
			WriteToOutputFile (textOut, Customer, Charge, counter);
		}
		else
		{
			return 1;
		}

		DisplayChargesForCustomers (textOut, counter, Customer, userCustomerCode);

		system ("PAUSE");
		return 0;
	}
	else
	{
		return 1;
	}

	// CLOSE FILE!!!!!!
}

bool OpenAndValidateInputFile (ifstream& textIn)
{
    // open input file
    textIn.open ("CUSTOMERS.TXT");

	// check if file opens successfully
	// if not, print a warning and exit program from main with a return code 1
	if (!textIn.is_open ())
	{
		return false;
	}
	else
	{
		return true;
	}
}// end OpenAndValidateInputFile

void ReadAndStoreInputFile (ifstream& textIn, string Customer[], double Charge[], int& counter)
{
	string customerCode;													// customer ID code - unique 4 capital letters followed by 4 digits
	double utilityCharge = 0;												// utility charge per unit

	// while file is still readable, and peek does not find end-of-file
	while (textIn.good () && textIn.peek () != EOF)
	{
		// read in data from CUSTOMERS.TXT
		textIn >> customerCode;
		textIn >> utilityCharge;

		// if the file contains too many lines of data, stop reading data and issue warning
		if (counter >= MAX_CUSTOMERS)
		{
			cout << "Error: file contains too many lines of data" << endl;
		}
		else
		{
			Customer [counter] = customerCode;

			Charge [counter] = utilityCharge;

			counter++;
		}
			
		// read newline
		textIn.get ();
	}
}// end ReadAndStoreInputFile

void SelectionSort (string Customer [], double Charge [], int counter)
{
	// local variables
	int i;																	// integer place holder i
	int j;																	// integer place holder j
	int max;																// place holder for highest letter found for sort

	// setting parameter for i
	for (i = 0; i < counter - 1; i++)
	{
		max = i;

		// setting parameter for j
		for (j = i + 1; j < counter; j++)
		{
			// searching through array, and replacing lower value higher value if found
			if (Customer [j] > Customer [max])
			{
				max = j;
			}
		}

		if ( max != i ) 
		{	
			string tempString = Customer[i];
			Customer[i] = Customer[max];
			Customer[max] = tempString;

			// aligning Charge [] with Customer []
			double tempDouble = Charge[i];
			Charge[i] = Charge[max];
			Charge[max] = tempDouble;
		}
	}
} // end SelectionSort

bool OpenAndValidateOutputFile (ofstream& textOut)
{
    // open input file
    textOut.open ("SORTED.TXT");

	// check if file opens successfully
	// if not, print a warning and exit program from main with a return code 1
	if (!textOut.is_open ())
	{
		return false;
	}
	else
	{
		return true;
	}
}// end OpenAndValidateOutputFile

void WriteToOutputFile (ofstream& textOut, string Customer [], double Charge [], int counter)
{
	// write each instance to output file for Customer [] and Charge []
	for (int i = 0; i < counter; i++)
	{
		textOut << Customer [i] << showpoint << fixed << setprecision (2) << setw (8) << Charge [i] << endl;
	}
}// end WriteToOutputFile

void DisplayChargesForCustomers (ofstream& textOut, int counter, string Customer [], string userCustomerCode)
{
	cout << "CUSTOMER CODES on file are: " << endl << endl;

	for (int i = 0, lines = 0; i < counter; ++i)
	{
		cout << setw (11) << Customer [i];

		if (++lines > 5)
		{
			lines = 0;
			cout << endl;
		}
	}

	cout << endl << endl;

	while (GetUserInput (userCustomerCode))
	{
		ValidateCustomerCode (userCustomerCode, counter, Customer);

		BinarySearchForCustomerCode (userCustomerCode, counter, Customer);
	}


}// end DisplayChargesForCustomers

bool GetUserInput (string &userCustomerCode)
{
	cout << "Enter a customer code (or E to exit): ";

	return (cin >> userCustomerCode && userCustomerCode != "E" && userCustomerCode != "e");
}// end GetUserInput

void ValidateCustomerCode (string& userCustomerCode, int counter, string Customer [])
{
	// local variables
	string tempA;
	string tempB;

	cout << endl;

	tempA = userCustomerCode.substr (0, 4);
	tempB = userCustomerCode.substr (4, 4);

	for (unsigned int i = 0; i < tempA.length (); i++)
	{
		tempA [i] = toupper (tempA [i]);
	}

	if (userCustomerCode.length () != maxStringSize)
	{
		cout << "Invalid Entry! Customer code " << userCustomerCode << " is too long." << endl;
		cout << "Must be 4 letters followed by 4 digits. Try again." << endl;
	}
	else if (!isalpha (tempA [maxTempSize]))
	{
		cout << "Invalid Entry! Customer Code " << userCustomerCode << " is formatted incorrectly." << endl;
		cout << "Must be 4 letters followed by 4 digits. Try again." << endl;
	}
		
	for (unsigned int i = 0; i < tempB.length (); i++)
	{
		if (!isdigit (tempB [i]))
		{
			cout << "Invalid Entry! Customer Code " << userCustomerCode << " is formatted incorrectly." << endl;
			cout << "Must be 4 letters followed by 4 digits. Try again." << endl;
		}
	}
}// end ValidateCustomerCode

void BinarySearchForCustomerCode (string userCustomerCode, int counter, string Customer [])
{
	int position;
	int comparisonCount = 1;
	int low = 0;
	int high = counter -1;

	position = (low + high) / 2;

	while ((Customer [position] != userCustomerCode) && (low <= high))
	{
		comparisonCount++;

		if (Customer [position] > userCustomerCode)
		{
			high = position - 1;
		}
		else
		{
			low = position + 1;
		}
		
		position = (low + high) / 2;
	}

	if (low <= high)
	{
		cout << position << endl;
	}
	else
	{
		cout << "Not found" << endl;
	}
}// end BinarySearchForCustomerCode 

[scu1casper]

I am having some issues getting the Binary Search to work.

Long Story short: I have a text file that uses a parallel array to store customerCode and utilityCharge per customer. I sorted the arrays in descending order by customerCode.

I then displayed the stored customerCodes on the console, and asked the user to enter his/her customerCode.

My intention is to use a binary search to find the customerCode the user entered, and thus...display the found customerCode along with the appropriate charges...if nothing is found, an error should pop up saying nothing was found.

Any help would be greatly appreciated. Currently, if I enter lower case letters, it finds NOTHING...EVER...if i enter uppercase letters, it ONLY finds what is in position 4

[AbstractionAnon]

What does your input file look like?

[scu1casper]

GREG2236 333.77
ANGE9271 109.48
TROY6385 178.47
VINC1347 65.02
FRAN5782 312.43
JENN0928 112.98
JIMM1942 98.12
QUIN4398 39.97
LYNS1028 132.77
NORI4389 111.92

[scu1casper]

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <algorithm>
using namespace std;

// global constants
const int MAX_CUSTOMERS = 1000;
int maxStringSize = 8;
int maxTempSize = 3;
const int NOT_FOUND = -1;

// function prototypes
bool OpenAndValidateInputFile (ifstream& textIn);
void ReadAndStoreInputFile (ifstream& textIn, string Customer[], double Charge[], int& counter);
void SelectionSort (string Customer[], double Charge [], int counter);
bool OpenAndValidateOutputFile (ofstream& textOut);
void WriteToOutputFile (ofstream& textOut, string Customer [], double Charge [], int counter);
void DisplayChargesForCustomers (ofstream& textOut, int counter, string Customer [], string userCustomerCode);
bool GetUserInput (string &userCustomerCode);
string ValidateCustomerCode (string& userCustomerCode, int counter, string Customer []);
void BinarySearchForCustomerCode (string userCustomerCode, int counter, string Customer []);

int main()
{
	// local variables
	ifstream textIn;														// input file stream variable
	ofstream textOut;
	string Customer [MAX_CUSTOMERS];
	double Charge [MAX_CUSTOMERS];
	int counter = 0;
	string userCustomerCode;

	if (OpenAndValidateInputFile (textIn))
	{
		ReadAndStoreInputFile (textIn, Customer, Charge, counter);

		SelectionSort (Customer, Charge, counter);

		if (OpenAndValidateOutputFile (textOut))
		{
			WriteToOutputFile (textOut, Customer, Charge, counter);
		}
		else
		{
			return 1;
		}

		DisplayChargesForCustomers (textOut, counter, Customer, userCustomerCode);

		ValidateCustomerCode (userCustomerCode, counter, Customer);

		BinarySearchForCustomerCode (userCustomerCode, counter, Customer);

		system ("PAUSE");
		return 0;
	}
	else
	{
		return 1;
	}

	// CLOSE FILE!!!!!!
}

bool OpenAndValidateInputFile (ifstream& textIn)
{
    // open input file
    textIn.open ("CUSTOMERS.TXT");

	// check if file opens successfully
	// if not, print a warning and exit program from main with a return code 1
	if (!textIn.is_open ())
	{
		return false;
	}
	else
	{
		return true;
	}
}// end OpenAndValidateInputFile

void ReadAndStoreInputFile (ifstream& textIn, string Customer[], double Charge[], int& counter)
{
	string customerCode;													// customer ID code - unique 4 capital letters followed by 4 digits
	double utilityCharge = 0;												// utility charge per unit

	// while file is still readable, and peek does not find end-of-file
	while (textIn.good () && textIn.peek () != EOF)
	{
		// read in data from CUSTOMERS.TXT
		textIn >> customerCode;
		textIn >> utilityCharge;

		// if the file contains too many lines of data, stop reading data and issue warning
		if (counter >= MAX_CUSTOMERS)
		{
			cout << "Error: file contains too many lines of data" << endl;
		}
		else
		{
			Customer [counter] = customerCode;

			Charge [counter] = utilityCharge;

			counter++;
		}
			
		// read newline
		textIn.get ();
	}
}// end ReadAndStoreInputFile

void SelectionSort (string Customer [], double Charge [], int counter)
{
	// local variables
	int i;																	// integer place holder i
	int j;																	// integer place holder j
	int max;																// place holder for highest letter found for sort

	// setting parameter for i
	for (i = 0; i < counter - 1; i++)
	{
		max = i;

		// setting parameter for j
		for (j = i + 1; j < counter; j++)
		{
			// searching through array, and replacing lower value higher value if found
			if (Customer [j] > Customer [max])
			{
				max = j;
			}
		}

		if ( max != i ) 
		{	
			string tempString = Customer[i];
			Customer[i] = Customer[max];
			Customer[max] = tempString;

			// aligning Charge [] with Customer []
			double tempDouble = Charge[i];
			Charge[i] = Charge[max];
			Charge[max] = tempDouble;
		}
	}
} // end SelectionSort

bool OpenAndValidateOutputFile (ofstream& textOut)
{
    // open input file
    textOut.open ("SORTED.TXT");

	// check if file opens successfully
	// if not, print a warning and exit program from main with a return code 1
	if (!textOut.is_open ())
	{
		return false;
	}
	else
	{
		return true;
	}
}// end OpenAndValidateOutputFile

void WriteToOutputFile (ofstream& textOut, string Customer [], double Charge [], int counter)
{
	// write each instance to output file for Customer [] and Charge []
	for (int i = 0; i < counter; i++)
	{
		textOut << Customer [i] << showpoint << fixed << setprecision (2) << setw (8) << Charge [i] << endl;
	}
}// end WriteToOutputFile

void DisplayChargesForCustomers (ofstream& textOut, int counter, string Customer [], string userCustomerCode)
{
	cout << "CUSTOMER CODES on file are: " << endl << endl;

	for (int i = 0, lines = 0; i < counter; ++i)
	{
		cout << setw (11) << Customer [i];

		if (++lines > 5)
		{
			lines = 0;
			cout << endl;
		}
	}

	cout << endl << endl;

	while (GetUserInput (userCustomerCode))
	{
		ValidateCustomerCode (userCustomerCode, counter, Customer);

		BinarySearchForCustomerCode (userCustomerCode, counter, Customer);
	}


}// end DisplayChargesForCustomers

bool GetUserInput (string &userCustomerCode)
{
	cout << "Enter a customer code (or E to exit): ";

	return (cin >> userCustomerCode && userCustomerCode != "E" && userCustomerCode != "e");
}// end GetUserInput

string ValidateCustomerCode (string& userCustomerCode, int counter, string Customer [])
{
	// local variables
	string tempA;
	string tempB;

	cout << endl;

	tempA = userCustomerCode.substr (0, 4);
	tempB = userCustomerCode.substr (4, 4);

	if (userCustomerCode.length () != maxStringSize)
	{
		cout << "Invalid Entry! Customer code " << userCustomerCode << " is too long." << endl;
		cout << "Must be 4 letters followed by 4 digits. Try again." << endl;
	}
	else if (!isalpha (tempA [maxTempSize]))
	{
		cout << "Invalid Entry! Customer Code " << userCustomerCode << " is formatted incorrectly." << endl;
		cout << "Must be 4 letters followed by 4 digits. Try again." << endl;
	}
		
	for (unsigned int i = 0; i < tempB.length (); i++)
	{
		if (!isdigit (tempB [i]))
		{
			cout << "Invalid Entry! Customer Code " << userCustomerCode << " is formatted incorrectly." << endl;
			cout << "Must be 4 letters followed by 4 digits. Try again." << endl;
		}
	}


	for (unsigned int i = 0; i < tempA.length (); i++)
	{
		tempA [i] = toupper (tempA [i]);
	}

	return userCustomerCode = tempA + tempB;
}// end ValidateCustomerCode

void BinarySearchForCustomerCode (string userCustomerCode, int counter, string Customer [])
{
	int position;
	int comparisonCount = 1;
	int low = 0;
	int high = counter -1;

	position = (low + high) / 2;

	while ((Customer [position] != userCustomerCode) && (low <= high))
	{
		comparisonCount++;

		if (Customer [position] > userCustomerCode)
		{
			high = position - 1;
		}
		else
		{
			low = position + 1;
		}
		
		position = (low + high) / 2;
	}

	if (low <= high)
	{
		cout << position << endl;
	}
	else
	{
		cout << "Not found" << endl;
	}
}

[scu1casper]

Ok, i switched some stuff around to make the flow more efficient, and got the "toupper" working. So now, when the user inputs their customer code, it stores it as upper case before seaching.

Now, the only issue I am having...is the binary search. I cannot figure out what I am doing wrong. This is almost exactly what the example was that i was given in class.