binarysearch.cpp

说明：一个二分检索算法例子。有详细的注释

/*
	Ian Davis
	cpsc122
	idavis
	asgn3
*/

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

int read(ifstream& dataIn, char* []);
//Task: Read dataIn a character at a time into input.
//      The records in dataIn correspond to rows in the array.
//Pre:  dataIn exists and has been opened
//Post: input contains dataIn with the end of line characters
//      replaced by null characters. returns the number of records read

void gOpenIn(char* argv[], ifstream& dataIn);
//Pre: argv[1] is a file name, dataIn has been declared to be of type ifstream.
//Post:  dataIn is open if dataIn refers to an existing file else
//       program invokes exit(1).

int BinarySearch(char key[20], char* stringArray[], int size);
//Pre:	key is a cstring, stringArray is a pointer arrey and have been initialized
//	size is the number of elements pointed to by stringArray
//Post:	If key if found, returns line on which found, else returns not found

int main(int argc, char* argv[])
{
    ifstream dataIn;
    gOpenIn(argv, dataIn);
	char* stringArray[40];
    int found = 0;
    char key[20];
	char ans = 'n', wierd;

    int howMany = read(dataIn,stringArray);
		
	do{
		cout << "\nEnter a String to search for: ";
		cin.getline(key, 20);

		found = BinarySearch(key, stringArray, howMany - 1) + 1;
	
		if(found)
			cout << key << " was found at position " << found << endl;
		else
			cout << key << " was not found." << endl;
		
		cout << "Whould you like to search for another string?\n";
		cin.get(ans);
		cin.get(wierd);		

	}while(ans == 'y' || ans == 'Y');

	dataIn.close();
	return 0;
}

//Task: Read dataIn a character at a time into input.
//      The records in dataIn correspond to rows in the array.
//Pre:  dataIn exists and has been opened
//Post: input contains dataIn with the end of line characters
//      replaced by null characters. returns the number of records read
int read(ifstream& dataIn, char* stringArray[])
{
	int i = 0, j = 0, len = 0;
	char input[40];
	dataIn.get(input[j]);
	while (!dataIn.eof())
	{
		if(input[j] == '\n')
		{
			input[j] = '\0';
			len = strlen(input);
			stringArray[i] = new char[len + 1];
			strcpy(stringArray[i], input);
			j = 0;
			i++;
		}
		else
			j++;

		dataIn.get(input[j]);
	}
	return i;
}

//Pre: argv[1] is a file name, dataIn has been declared to be of type ifstream.
//Post:  dataIn is open if dataIn refers to an existing file else
//       program invokes exit(1).
void gOpenIn(char* argv[], ifstream& dataIn)
{
	dataIn.open(argv[1]);

	if (dataIn.fail())
	{
		cout << "Open of Input File Failed\n";
		exit(1);
	}
}

//Pre:  key is a cstring, stringArray is a pointer arrey and have been initialized
//      size is the number of elements pointed to by stringArray
//Post: If key if found, returns line on which found, else returns not found
int BinarySearch(char key[20], char* stringArray[], int size)
{
	int lo = 0;
	int hi = size;
	int mid;

	while (lo <= hi)
	{
		mid = (lo + hi) / 2;

		if (strcmp(key,stringArray[mid]) == 0)
			return mid;
		if (strcmp(key,stringArray[mid]) < 0)
			hi = mid - 1;
		else											
			lo = mid + 1;
	}

	return -1;
}