bool関数を使用したC++での再帰バイナリ検索

Question

私は再帰バイナリ検索関数を作成する必要のある学校の割り当てを持っています。私は関数の署名を変更することはできません。 私のポインターの経験は最高ではないし、私の問題はそこにあると思う。 私はStackoveflowを取得するが、私は本当に道

bool contains(const int* pBegin, const int* pEnd, int x) 
{ 
    int length = pEnd - pBegin;//gives me the length of the array 
    const int* pMid = pBegin + (length/2); 
    if(length == 1) 
    { 
     if(*pMid != x) 
      return false; 
     return true; 
    } 
    else if(x < *pMid) 
     return contains(pBegin, pMid-1, x); 
    else 
     return contains(pMid, pEnd, x); 
} 

void main(){ 
    setlocale(LC_ALL, "swedish"); 
    int arr[10]; 
    for(int i = 0; i < 10; ++i) 
     arr[i] = i; 
    bool find = contains(&arr[0], &arr[10], 3);//arr[10] points to the index after the array! 
    cout <<"found = "<< find << endl; 
    system("pause"); 
} 

理解しない誰かが私が間違ってやっているものを私に説明していただけますし、どのように私はより良い方法でそれを行うだろうか？

Answer 1

スタックオーバーフローは深すぎる再帰によるものです。 あなたの配列は本当に問題になるほど大きいので、無限の再帰があります。contains（）は自分自身を呼び出し続け、これを検出することはできません。

これがどのように可能かを見て、アサーションを追加してください。

あなたのコードは、あなたのコードは、この可能性に対応していない PEND> PBEGIN

を前提としています。

#include <assert.h> 
bool contains(...) 
{ 
    assert(pBegin > pEnd); 
    ... 

ここでは、この前提が正しくない場合は中断します。

（pEnd> pBegin）が「<」または「==」のfalseの可能性が2つあります。 あなたのコードは、この2つのケースで何をしますか？

以下スポイラー..

長さがゼロであることができ、処理されません。