下面的代码有什么问题?为什么使用我的二进制搜索实现没有找到这封信?
#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;
}
最佳答案
二分查找的先决条件是数组应该排序。
要对字符串 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
等名称。
关于c++ - 对 C++ 字符串的二进制搜索不起作用,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3860896/