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(あなたの場合はm) をmid+1(あなたの場合は ) に変更しますk+1。同様に、他のケースも変更する必要があります。

と

while (m!=n)

する必要があります

while (m<=n)

なんで？

'a'string でchar を検索する場合を考えてみましょう"a"。あなたのmとの両方nが になり0、 そうなりますk. あなたの場合、 while ループはまったく入力されていません。したがって、一般に、検索が 1 つの要素に絞り込まれ、それがたまたまキーになると、既存のコードは失敗します。

ヒント：

変数名の選択が適切ではありません。low、 、highなどの名前を使用することをお勧めしますmid。

于 2010-10-05T04:46:27.847 に答える