3

私の問題は、開始するたびにローをゼロに設定していることだと99％確信しています。しかし、再帰の深さに関係なく、低いインデックスを一貫して表すように低く保つ方法がわかりません。低指数の指数を正確に教えてくれれば、問題ないと思います。

これまでの私のコードは次のとおりです。

int recBSearch(vector<int> v, int size, int item)
{
    int index = size / 2;
    int curr = v[index];
    int low = 0;
    int high = size -1;
    if (v[index] == item)
        return index;
    else if (v[index] > item)
    {
        high = index;
        index = (high+low)/2;
        size = high - low;
        return recBSearch(v, size, item);
    }
    else if (v[index] < item)
    {
        low = index;
        index = (high+low)/2;
        size = high - low;
        return recBSearch(v, size, item);
    }
    return -1;
}
4

3 に答える 3

6

ベクトルの上半分を検索しようとしている場合、これは機能しません。実際に作成する必要があるのはベクトルのスライスだからです。

バイナリ検索は既にありますが、独自に作成する場合は、パラメーターで iterator-range を使用してください。(2 つの単純なイテレータまたはブースト範囲を渡すことができます)。

イテレータの場所が見つからない場合は -1 が必要なので、スライス (イテレータ範囲) で、見つかった場合に備えて開始インデックス番号を指定する必要があります。

別の方法として、ベクトル (const 参照による) と検索する範囲を渡すこともできます。

最後の行に到達できません。代わりに、評価を行う前に再帰の終了条件にする必要があります。(範囲が空の場合)

参照渡しとインデックス番号を使用して反復するバージョン (最も単純) は、次のようになります。

int recBSearch( std::vector<int> const& vec, int start, int end, int value )
{
    if( start == end )
    {
       return -1;
    }
    int index = (start + end) / 2;
    // continue from here
}

endは「最後の要素の 1 つ後」を示すため、ベクトルのサイズが 5 の場合、最初の反復は 0 と 5 を渡します。ベクトルが空の場合は、0 と 0 を渡します。

練習問題として「3つのパラメータでできるか」？

はい...

 typedef std::vector<int>::const_iterator citer;
 int recBSearch( citer start, citer end, int value )
 {
    if( start == end )
    {
       return -1;
    }
    citer middle = start + (end-start)/2;
    if( *value == *middle )
    {
       return middle - start;
    }
    else if ( *value < *middle )
    {
       return recBSearch( start, middle, value );
    }
    else // note the change here
    {
        int res = recBSearch( middle+1, end, value );
        if( res == -1 )
           return -1;
        else
           return res + 1 + (middle-start);
    }
 }
于 2012-10-24T11:42:38.813 に答える
2

再帰的に実行したい場合、メソッドは検索範囲をパラメーターとして受け取る必要があります。それ以外の場合は、関数に常に完全なベクトルを与えると仮定して、rucursive 呼び出しで検索する場所を追跡できません。

したがって、メソッドの署名は次のようになります。

int recBSearch(vector<int> v, int first, int last, int item)
于 2012-10-24T11:41:20.467 に答える
0

二分探索は基本的に、範囲を半分に分割し、それぞれを検索することで機能します。あなたのコードは、両方のブランチの下半分で操作していることを示しています。の代わりに、vベクトルの上位半分を再帰呼び出しに渡す必要があります。else ifsize/2size

于 2012-10-24T11:41:11.480 に答える