c++ - 再帰を使った二分探索

Question

これがキーを返さない理由がわかりません。ステップをスキップしているようです。私が感じるロジックはまっすぐです。midptr がキーよりも小さい場合は右に検索し、そうでない場合は左側を検索します。しかし、それはキーを返さないので、-1 を返します。ヘルプ？ここにコードと関数があります

#include<iostream>
using namespace std;


int binsrch(int *raw, unsigned int size, int key);




int main()
{
  int raw[] = {1,3,5,7,11,23, 48};
  cout << binsrch(raw, 7, 11) << endl;


  system("pause");
  return 0;
}



int binsrch(int *raw, unsigned int size, int key)
{
    int *begptr, *endptr ,*midptr;
//see if we already have the key

if(*raw == key)
  return key;

begptr = raw;
endptr = raw + (size - 1);
midptr = raw + (size / 2);

cout << "#" <<*midptr << " size:" << size<<  endl;
if(*midptr == key)
{
  return key;
}
else  if( *midptr < key) //Search Right
{
  cout << "#" <<*(midptr+1) << " size:" << size<<  endl;
  binsrch(midptr + 1, size / 2, key);
}
else if(*midptr > key) //Search Left
{
    cout << " #" <<*midptr << " size:" << size<<  endl;
    binsrch(begptr, size / 2, key);
}

return -1;
}

score 5 · Accepted Answer

returnあなたは声明を忘れました。再帰呼び出しの結果を返す必要があります。

binsrch(midptr + 1, size / 2, key);

する必要があります

return binsrch(midptr + 1, size / 2, key);

-1そうしないと、最初の再帰の前にキーが見つからない限り、最初の呼び出しで本体の残りの部分が実行され、常にが返されます。

return ステートメントを追加することで、再帰呼び出しの制御フローを中断し (つまり、「見つかりません」の値を返さない)、最初の戻り値まで、最後の戻り値を呼び出しスタックに伝播します。呼び出し、最後に必要な値を返します。

score 0 · Accepted Answer

すべて正常に動作しますが、正しい値が返されません。else-if-statements では、関数を再帰的に呼び出しますが、戻り値は最初の呼び出しに渡されません! 試す：

return binsrch(midptr + 1, size / 2, key);

と

return binsrch(begptr, size / 2, key);

それはうまくいくはずです。

-編集:まあ、私は遅くなったと思います;)

score 0 · Accepted Answer

次も追加する必要があります。

if(endptr == midptr) return -1;

endptr を計算した後、21.. などの配列にない要素を検索する場合の無限ループを回避します。

c++ - 再帰を使った二分探索

3 に答える 3

Related

Reference