二进制搜索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.