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

Answer 2

你每次錯了一半。 （如果strcmp大於零，搜索項會更大，因此您需要查看高半部分（即變低）。）