Help with Implementation of binary search for names in an array of structs
I need to use a binary search to find a requested name in an array of structs. I used a binary search example code that searched ints and modified it to search through the array indecies to compare the names in each struct. The program runs but the name is never found so something is definitely going wrong somewhere. Not sure if it is the way I am taking in the name from the stream or just my implementation of the search in general. Can anyone take a look provide some feed back? thanks
relevent code from the input function:
char entryName[31];
char discard;
string entryNameString;
cout << "What is the name of the entry you would like to look up?" << endl;
cin >> entryNameString;
cin.get(entryName, 30);
cin.get(discard);
findName(listLength, arrayOfStruc开发者_JAVA百科ts, entryName);
the binary search function:
void findName(int listLength, contactInfo* arrayOfStructs, const char* entryName)
{
bool found = false;
int low = 0, high = listLength-1, mid;
while (!found && low <= high)
{
mid = (low + high) / 2;
if (strcmp(entryName, arrayOfStructs[mid].contactName) == 0)
found = true;
else
if (strcmp(entryName, arrayOfStructs[mid].contactName) < 0)
high = mid - 1;
else
low = mid + 1;
}
if (found)
{
cout << arrayOfStructs[mid].contactName << endl;
cout << arrayOfStructs[mid].birthday << endl;
cout << arrayOfStructs[mid].addressInfo.streetName << endl;
cout << arrayOfStructs[mid].addressInfo.cityName << endl;
cout << arrayOfStructs[mid].addressInfo.state << " ";
cout << arrayOfStructs[mid].addressInfo.zipcode << " ";
cout << arrayOfStructs[mid].addressInfo.phoneNumber << endl;
cout << arrayOfStructs[mid].typeOfentry << endl;
}
else
cout << "NOT FOUND" << endl;
}
EDIT: arrayOfstructs[].contactName is ordered alphabetically, (e.g. .contactName = Amanda, is located in a smaller index than .contactName = Zorak)
In case you try to enter names separated by whitespace you need to use std::getline
instead of istream::operator>>
.
Since you also asked for general feedback. Notice that your are potentially comparing the same strings twice for each iteration. strcmp returns whether its less, equal or greater (-1,0,1). You could get the return value and perform all futher comparisons with that...
int result = strcmp(entryName, arrayOfStructs[mid].contactName);
if (result == 0)
found = true;
else
if (result < 0)
high = mid - 1;
else
low = mid + 1;
精彩评论