binary search help

Since I'm new in C++ I need some help with this program that is to write a telephone lookup programs. Read a data set of 1000 names and telephone numbers from a file that contains the numbers in random order. Handle lookups by name and also reverse lookups by phone number. Use binary search for both lookups. So far I have only this. Can I get a little help on that


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



void findNameAndPrint(string nameToFind, string names[1000],
int phoneNumbers[1000], int numberRead);
int readNamesAndNumbers( string names[1000], int numbers[1000]);

int main(void) {
int phoneNumbers[1000];
string names[1000];
int numberRead;
string nameToFind;

numberRead = readNamesAndNumbers(names, phoneNumbers);

cout << "Input the name to lookup ";
cin >> nameToFind;

findNameAndPrint(nameToFind, names, phoneNumbers, numberRead);

return EXIT_SUCCESS;

}


int readNamesAndNumbers ( string names[1000], int numbers[1000])
{

int numberRead = 0; // Initially no values have been read.

ifstream phoneFile;

phoneFile.open("HWData.txt");

while (phoneFile.good()) {
phoneFile >> names[numberRead] >> numbers[numberRead];
if (phoneFile.good()) {
numberRead++;
}
}

return numberRead;
}

void findNameAndPrint(string nameToFind, string names[1000],
int phoneNumbers[1000], int numberRead)
{
int current;

for (current = 0; current < numberRead; current++) {
if (names[current] == nameToFind) {
cout << names[current] << " " << phoneNumbers[current] << endl;
}
}
return;
}

I wrote a binary search for someone a while back. Search through the history of this forum and you should find code to do it.

-KM-

In order to do a true binary search on a list of randomly ordered data, you would need to dynamically sort the data first.

The concept of a binary search is that you start somewhere in the 'middle', check if your search value is higher or lower than the the current position and then jump to half way between that 'correct' half of the data and repeat until you narrow it down to a match.

My suggestion would be to write a function to sort the data dynamically into an array(in effect, create an index), then perform a standard binary search on it.

Hope this helps!

Hello,

Because you have to do a search on both the name and the telephone
number this means you are using 2 different types of indexes.

What you should do is make an index (ie: array of type) for both the
telephone numbers and the names, the index element in each would be
a pair containing the key (ie: tel number or name) and a position
pointing to the 3rd array where both the telephone and names are
stored. The 3rd array does not need to be sorted however both index
arrays should be sorted according to the keys (ie: tel number or name).

struct
{
char* telephone;
unsigned int position;
} TelephoneElement

struct
{
char* name;
unsigned int position;
} NameElement

struct
{
char* name;
unsigned int position;
} CombinedElement


The indexes would like like this:

TelephoneElement* telephoneIndex = new TelephoneElement[NUMBER_OF_ELEMENTS];
NameElementElement* nameIndex = new NameElement[NUMBER_OF_ELEMENTS];
CombinedElement* mainIndex = new CombinedElement[NUMBER_OF_ELEMENTS];


[.] populate all 3 indexes accordingly.
[.] sort the telephoneIndex and the nameIndex


Now you have the necessary infrastructure to perform a binary search on either
the name or the telephone number.


Arash Partow
__________________________________________________
Be one who knows what they don't know,
Instead of being one who knows not what they don't know,
Thinking they know everything about all things.
http://www.partow.net