C++二进制搜索没有成功运行......永远

Question

编辑:澄清一下，我正在搜索的对象数组确实已按搜索变量的字母数字顺序进行了预排序。

我做了一个二分搜索函数并将它嵌套在另一个函数中。出于某种原因，每次我使用二进制搜索都无法找到相关的字符数组。

基本上，二进制搜索应该通过 getAccountNumber() 的返回值搜索名为 credArray 的对象数组中的每个对象。二分查找总是返回 -1。

整个程序编译良好，只是没有产生正确的结果。使用对象数组的方法也适用于其他地方，所以这不是问题。我知道我犯了一些非常简单的错误，但我没有看到。这是两个函数:

//This function uses binary search to search for the relevant account
int AccountDB::searchForAccount(char* searchNumber)
{
    int low = 0;
    int high = accountsAmount - 1;
    int mid;
    //now for the loop, using strcmp because these are C strings
    while (low<=high)
    {
        mid = (low + high) / 2;
        if (strcmp(searchNumber,credArray[mid].getAccountNumber()) == 0)
            return mid;
        if (strcmp(searchNumber,credArray[mid].getAccountNumber()) > 0)
            high = mid -1;
        else
            low = mid + 1;
    }
    return -1;
}
//This function records the transactions and writes the output to an external file
void AccountDB::processTransactions(const char* transactFile)
{
    //set up the input stream from the text file
    ifstream inFile;
    //set up the variables to be read from text file
    char date[6];
    char type;
    char accountnumber[20];
    double amount; 

    //open the file
    inFile.open(transactFile);
    //standard check for file and exit if it doesn't exist
    if(!inFile)
    {
        cout << "Error, input file could not be opened.\n";
        exit(1);
    }
    //Creates a header for listing transactions
    cout << setw(5) << "Date"
         << setw(25) << "Account Number"
         << setw(5) << "Type"
         << setw(8) << "Amount"
         << setw(30) << "New Balance"
         << endl;
         inFile >> date;
         while (inFile)
         {
            inFile >> accountnumber >> type >> amount;
            cout << setw(5) << date
                 << setw(25) << accountnumber
                 << setw(5) << type
                 << setw(8) << amount;
            int relevantAccount = searchForAccount(accountnumber);
            cout << "\nThe searchForAccount returned " << relevantAccount << " by the way\n";
            if (relevantAccount != -1)
            {
                if (type == 'P')
                {
                    credArray[relevantAccount].processPayment(amount);
                    cout << setw(30) << credArray[relevantAccount].getBalance() << endl;
                }
                else
                {
                    bool chargestatus = credArray[relevantAccount].processCharge(amount);
                    if (chargestatus = 1)
                        cout << setw(30) << credArray[relevantAccount].getBalance() << endl;
                    else
                        cout << "Credit limit exceeded" << endl;
                }
            }
            else
                cout << "Invalid account number" << endl;   
            inFile >> date;
        }
        cout << "End of transaction list." << endl;
}

Answer 1

你是对的，有一个非常简单的小错误。当第一个字符串大于第二个字符串时，strcmp()返回值比较大于0。这意味着您的比较应该被翻转。

固定代码如下:

int AccountDB::searchForAccount(char* searchNumber)
{
    int low = 0;
    int high = accountsAmount - 1;
    int mid;
    //now for the loop, using strcmp because these are C strings
    while (low<=high)
    {
        mid = (low + high) / 2;
        if (strcmp(searchNumber,credArray[mid].getAccountNumber()) == 0)
            return mid;
        if (strcmp(searchNumber,credArray[mid].getAccountNumber()) < 0) // this is now "<"
            high = mid -1;
        else
            low = mid + 1;
    }
    return -1;
}

更新:小优化

考虑进行此更改以使其运行得更快一些，也更易于阅读。

    while (low<=high)
    {
        mid = (low + high) / 2;
        int val = strcmp(searchNumber,credArray[mid].getAccountNumber());
        if (val == 0)
            return mid;
        if (val < 0)
            high = mid -1;
        else
            low = mid + 1;
    }