Below is my code and the text files (ignore commented out lines). I'm having trouble getting the binary search method to work correctly. I have a sorted vector. I even have a for statement to print out the checks used in the binary search method and the checks inside the for loop and the print statement says it should be returning true. Thanks for any help! Tips/improvements on other parts of the code is also appreciated thank you!
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
vector<string> getVector(const string&);
string getName(const string&);
void selectionSort(vector<string>&);
bool search(const string&, const vector<string>&);
int main()
{
string boyName, girlName;
bool boyNameFound, girlNameFound;
vector<string> boyNames(getVector("BoyNames.txt"));
vector<string> girlNames(getVector("GirlNames.txt"));
/* debugging
for (vector<string>::const_iterator i = boyNames.begin(); i != boyNames.end(); ++i)
{
cout << *i << endl;
}
for (vector<string>::const_iterator i = girlNames.begin(); i != girlNames.end(); ++i)
{
cout << *i << endl;
}
*/
boyName = getName("boy's"); //getting the name of a boy and setting the var boyName = to it
//girlName = getName("girl's");
selectionSort(boyNames); //sort vector of popular boys names
//selectionSort(girlNames);
//boyNameFound = search(boyName, boyNames);
//girlNameFound = search(girlName, girlNames);
if(search(boyName, boyNames)){ cout << "boys true " <<endl;}
else{cout << "boys false"; }
// if(search(girlName, girlNames)){ cout << "girls true " <<endl;}
// else{cout << "girls false";}
}
vector<string> getVector(const string& ph){
vector<string> names;
ifstream namesFile(ph.c_str());
if (!namesFile){
cout << "Error opening file \n";
}
string line;
while(getline(namesFile,line)){
names.push_back(line);
}
names.push_back("end"); //to help when searching for names
return names;
}
string getName(const string& ph){
string name;
if(ph=="boy's"){ //when boys is selected
cout << "Enter a boys name or N to skip: ";
cin >> name;
}
else{ //when girls is selected
cout << "Enter a girls name or N to skip: ";
cin >> name;
}
return name;
}
bool search(const string& ph, const vector<string> &nameList){
bool nameInList;
cout << "The boys name we are searching for is " << ph <<endl; //printing out the name we are looking for. this is for debugging
cout << "TEST BINARY SEARCH: 0=false 1=true: " << binary_search (nameList.begin(), nameList.end(), ph) << endl;
if(binary_search (nameList.begin(), nameList.end(), ph)){
nameInList = true;
}
for(int y = 0; y < nameList.size(); y++)
{
cout << ph << " == " << nameList[y] << endl; //printing out for debugging
if (ph == nameList[y])
nameInList = true;
}
return nameInList;
}
void selectionSort(vector<string> &arr){ //selection sort works good
int startScan, minIndex;
string minValue;
for (startScan = 0; startScan < (arr.size() - 1); startScan++){
minIndex = startScan;
minValue = arr[startScan];
for(int index = startScan + 1; index < arr.size(); index++){
if (arr[index] < minValue){
minValue = arr[index];
minIndex = index;
}
}
arr[minIndex] = arr[startScan];
arr[startScan] = minValue;
}
}
TEXT FILE: BoysNames.txt
Jacob
Michael
Joshua
Matthew
Daniel
Christopher
Andrew
Ethan
Joseph
William
Anthony
David
Alexander
Nicholas
Ryan
Tyler
James
John
Jonathan
Noah
Brandon
Christian
Dylan
Samuel
Benjamin
Zachary
Nathan
Logan
Justin
Gabriel
Jose
Austin
Kevin
Elijah
Caleb
Robert
Thomas
Jordan
Cameron
Jack
Hunter
Jackson
Angel
Isaiah
Evan
Isaac
Mason
Luke
Jason
Gavin
Jayden
Aaron
Connor
Aiden
Aidan
Kyle
Juan
Charles
Luis
Adam
Lucas
Brian
Eric
Adrian
Nathaniel
Sean
Alex
Carlos
Bryan
Ian
Owen
Jesus
Landon
Julian
Chase
Cole
Diego
Jeremiah
Steven
Sebastian
Xavier
Timothy
Carter
Wyatt
Brayden
Blake
Hayden
Devin
Cody
Richard
Seth
Dominic
Jaden
Antonio
Miguel
Liam
Patrick
Carson
Jesse
Tristan
Alejandro
Henry
Victor
Trevor
Bryce
Jake
Riley
Colin
JaredJeremyMarkCadenGarrettParkerMarcusVincentKalebKadenBradyColtonKennethJoelOscarJosiahJorgeCooperAshtonTannerEduardoPaulEdwardIvanPrestonMaxwellAlanLeviStephenGrantNicolasOmarDakotaAlexisGeorgeCollinEliSpencerGageMaxCristianRicardoDerekMicahBrodyFranciscoNolanAydenDaltonShanePeterDamianJeffreyBrendan
TravisFernandoPeytonConnerAndresJavierGiovanniShawnBradenJonahCesarBradleyEmmanuelManuelEdgarErikMarioEdwinJohnathanDevonErickWesleyOliverTrentonHectorMalachiJalenRaymondGregoryAbrahamEliasLeonardoSergioDonovanColbyMarcoBrysonMartin
Remember that binary search only works on a sorted list. It starts with two variables l and r, which represent the left and right bounds that the name being searched for must lie between.
At each step, it creates a variable m = (l + r)/2 and compares the name at that index to the one being searched for. If the name is the one you're looking for, you're done. Otherwise if the name is greater, then set r to m and continue; and set l to m in the case that it is smaller.
Here is my code:
int binarySearch(const vector <string> &names, string name){
int l = 0, r = names.size();
while(l != r){
int m = (l+r)/2;
if(names[m] == name){return m;}
else if(names[m] > name){r = m;}
else{
l = m;
}
}
return -1; // name does not exist in the list
}
An alternative way to implement binary search is to implement it using jumps. This approach keeps one variable, curr, that represents the index being compared at the moment.
int curr = 0;
for(int i = names.size()/2; i >= 1; i /= 2){ // jump size
while(curr+i < names.size() && names[curr+i] <= name){
curr += i;
}
}
if(names[curr] == name){
// name was found at index curr
}
Both of these approaches center around the same idea, and their runtimes are pretty much identical. Using either one of these approaches should work for your program.
Your program also has a function selectionSort(), which I'm assuming is supposed to sort the std::vector before you execute a binary search algorithm. Note that C++ provides a general-use sorting function, std::sort(), which will run much quicker than selection sort in many cases. To use std::sort(), you must have typed #include <algorithm> somewhere in your program.