在C++字符串上進行二進制搜索不起作用

Question

以下代碼有什麼問題？如何使用我的二分查找實現找不到該字母？

#include <iostream> 
#include <string> 
#include <algorithm> 
#include <cctype> 
#include <cwctype> 
using namespace std; 

bool contains(string s, char a){ 
    int m = 0; 
    int n = s.length()-1; 

    while (m != n) { 
    int k = (m + n)/2; 
    if (s[k] == a) 
     return true; 

    if (s[k] < a) { 
     n = k - 1; 
    } else { 
     m=k + 1; 
    } 
    } 

    return false; 
} 

int main() { 

    string s = "miyvarxarmaiko"; 
    char a = 'm'; 
    if (contains(s,a) == true) { 
    cout << "s contains character a" << endl; 
    } else { 
    cout << "does not contain" << endl; 
    } 

    return 0; 
} 

Answer 1

一種用於二進制搜索的先決條件是該陣列應排序。

排序字符串s你可以做sort(s.begin(),s.end());

，我們在您執行了幾個錯誤：

if (s[k] < a) { 
    n = k - 1; // Incorrect..should be m = k + 1 
} else { 
    m= k + 1; // Incorrect..should be n = k - 1 
} 

爲什麼？

當關鍵是比你需要將搜索範圍縮小到中間元素的右半中間元素更多，你這樣做改變low（你的情況m）至mid+1（在你的情況k+1）。同樣，其他情況也需要改變。

和

while (m!=n) 

應該

while (m<=n) 

爲什麼？

考慮在字符串"a"中搜索char 'a'的情況。您的m和n將爲0，因此將爲k。在你的情況下，while循環根本不被輸入。因此，一般來說，當搜索縮小到一個元素並且恰好是您的密鑰時，您現有的代碼將會失敗。

提示：

你的變量名的選擇並不好。最好使用名稱，如low，high和mid。