c++ - 对 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 等名称。