2

以下代码有什么问题？为什么它没有使用我的二进制搜索实现找到字母？

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

1 回答 1

16

二分查找的一个先决条件是数组应该是有序的。

要对字符串进行排序，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(in your case m) 更改为mid+1(in your case k+1)。同样，其他情况也需要更改。

和

while (m!=n)

应该

while (m<=n)

为什么？

考虑'a'在字符串中搜索 char 的情况"a"。你m和n将是0，所以将是k。在您的情况下，根本没有输入 while 循环。因此，一般而言，当搜索范围缩小到一个元素并且恰好是您的关键时，您现有的代码将失败。

小费：

您的变量名选择不好。最好使用low,high和等名称mid。

于 2010-10-05T04:46:27.847 回答