c++ - 在 C++ 中对数组进行二进制搜索

Question

我的二进制搜索总是返回零，我不确定为什么。也许我错误地传递了我的论点？或者也许我没有正确归还它？我不太确定出了什么问题，如果有人能解释我如何返回我想要的值而不是零，谢谢。我的数组中充满了我没有包含那部分代码的单词，因为它是由一个文件填充的。我没有输入第一个词，所以我不应该得到零。我尝试了多个单词。

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


     //function prototypes
     void selectionSort(string[], int);
     int binarySearch(string[], int, string);

     int main()
  {
int open;
int name[8];
ifstream inputFile;
string filename;
int i = 0;
int size = 1024;
int newSize;
string exit;
string words[1024];
string word;
string newArray[1024];
string search;
int results;
string createdFile;
int startScan, minIndex, minValue;
//newArray[0]="This";


cout << "Please Enter the Filename: ";
cin >> filename;
inputFile.open(filename.c_str());
if (!inputFile) {
    cout << "Your File could not be opened!";
}
else if (inputFile) {

    while (i<1024) {
        inputFile >> word;
        //cout << i;
        if (word.length()<2) {              //gets rid of single character words
        i++;
        }
        else if(inputFile.eof()) {
        //cout<<newSize<<endl;
        newSize=i;
        //cout<< "DONE!"<<newSize;
        break;
        }
        else{
        newArray[i] = word;
        i++;
        //cout<<newArray[i]<<" " ;
        //newSize=1;



        //cout<<newSize;
        }

        //cout << newArray;
        //i++;
    }




}
inputFile.close();
//Take values stored in array and put them in another array with i number of elements

    string finalArray[i];
    size=i;
    for(int j = 0; j<i;j++)
        {
        finalArray[j]=newArray[j];

        //cout<<finalArray[j];
        }

cout << "Your document has been sorted. " << endl;
selectionSort(finalArray, size);
cout<< "Out putting Your array"<<endl;
for (int z = 0; z<size; z++) {
    cout << finalArray[z] << " ";
}

    cout << "Please insert a word to search!: " << endl;
    cin >> search;
    results = binarySearch(finalArray, size, search);
    cout << results << endl;
    //results = binarySearch(finalArray, size, search);
    //cout << results;
    cout << "To exit press 0, or enter another word..." << endl;



}//end of main


   void selectionSort(string array[], int size) {
int startScan, minIndex;
string minValue;

for (startScan = 0; startScan < (size - 1); startScan++)
{
    minIndex = startScan;
    minValue = array[startScan];
    for (int index = startScan + 1; index <size; index++) {
        if (array[index]<minValue) {
            minValue = array[index];
            minIndex = index;
        }
    }
    array[minIndex] = array[startScan];
    array[startScan] = minValue;

}
   }


   int binarySearch(string words[], int numElems, string word) {

int first = 0,                 //first array element
    last = numElems - 1,            //last array element
    middle,                        //mid point of search
    position = -1;                 //position of search value
bool found = false;            //flag

while (!found && first == last)
{
    middle = (first + last) / 2; //this finds the mid point
    if (words[middle] == word) {
        found = true;
        position = middle;
    }
    else if (words[middle]> word) // if it's in the lower half
    {
        last = middle - 1;
    }
    else {
        first = middle + 1;                 //if it's in the upper half
    }
    return position;

     }
   }//end binarySearch

Answer 1

问题是你有 return position;在while里面循环，但不在任何 if/else 中 block ，所以它在第一次迭代后返回，即使它还没有找到搜索字符串。你应该把它移到循环之后，或者在 if 中进行设置 position 的 block 当它找到匹配的元素时。

另一个问题是 while条件为真。你想在 first 时继续循环不等于last .实际上，这也不是正确的条件，因为如果数组只有一个元素，first和 last总是相等的，你会在测试它是否匹配之前停下来。所以正确的测试是while (first <= last) .

int binarySearch(string words[], int numElems, string word) 
{
    int first = 0,                 //first array element
    last = numElems - 1,            //last array element
    middle;                        //mid point of search

    while (first <= last)
    {
        middle = (first + last) / 2; //this finds the mid point
        if (words[middle] == word) {
            return middle;
        }
        else if (words[middle]> word) // if it's in the lower half
        {
            last = middle - 1;
        }
        else {
            first = middle + 1;                 //if it's in the upper half
        }
    }
    return -1;  // not found
}