c++ binary_search 排序数组的函数问题（流行名称搜索）

Question

下面是我的代码和文本文件（忽略注释掉的行）。我无法使二进制搜索方法正常工作。我有一个排序的向量。我什至有一个 for 语句来打印出二进制搜索方法中使用的检查和 for 循环内的检查，打印语句说它应该返回 true。谢谢你的帮助！ Tips/improvements对其他部分的代码也表示感谢谢谢！

#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;
    }
}

文本文件：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

Answer 1

请记住，binary search 仅适用于排序列表。它以两个变量 l 和 r 开头，它们表示要搜索的 name 必须位于的左右边界。

在每一步，它都会创建一个变量 m = (l + r)/2 并将该索引处的名称与正在搜索的名称进行比较。如果该名称是您要查找的名称，那么您就完成了。否则如果名称是大于，则将r设置为m并继续；如果较小，则将l设置为m。

这是我的代码：

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
}

另一种实现二分查找的方法是使用 jumps 来实现它。这种方法保留一个变量，curr，表示当前正在比较的索引。

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
}

这两种方法都围绕着同一个想法，并且它们的运行时间几乎相同。使用这些方法中的任何一种都应该适用于您的程序。

你的程序还有一个函数 selectionSort()，我假设它应该在你执行二进制搜索算法之前对 std::vector 进行排序。请注意，C++ 提供了一个通用的排序函数 std::sort()，在许多情况下，它运行比选择排序快得多。要使用 std::sort()，您必须在程序的某处输入 #include <algorithm>。

c++ binary_search 排序数组的函数问题（流行名称搜索）

c++ binary_search function trouble with sorted array (popular names search)

c++

vector

binary-search