-7

二分探索の再帰関数を作成します。
この関数は、ソートされた配列と検索する項目を受け入れ、項目のインデックス (項目が配列内にある場合) または -1 を返します (項目が配列内にない場合)。
さらに、関数をテストするテスト プログラムを作成します。 

template <class elemType>
int orderedArrayListType<elemType>::binarysearch
                                (const elemType& item) const
{
    int first= 0;
    int last = length -1;
    int mid;
    int list[];
    int BinarySearch(,Type & Item, int first, int last)
    bool found = false;
    while (first <= last && !found){
        mid = (first + last) / 2;
        if (list[mid] > item)
            return BinarySearch(list, item, first, mid -1)
        found = true;
        else if (list[mid] > item)
            return BinarySearch( list, item, first, mid -1)
            last = mid - 1;
        else 
            first = mid + 1;
    }
    if (found)
        return mid;
    else 
        return -1;
}
4

3 に答える 3

7

アメリカには子供向けのゲームがあり、一人の子供が 1 から 10 までの数字を選び、もう一人の子供がその数字を当てなければなりません。彼らが間違った推測をした場合、最初の子は「より高い」または「より低い」と言います。

ほとんどの子供はランダムに推測することから始め、成功するまでに平均で約 4 ～ 5 回試行します。私は（そしておそらくこれが私がコンピューターサイエンスに行き着いた理由です）、最善の方法は中間点を選ぶことだと気づきました（5.5なので、5か6のどちらかを選んでください。私は5.で行きます）。彼らの発言 (「より高い」または「より低い」) に基づいて、1 ～ 4 または 6 ～ 10 のいずれかの新しい範囲を選択します。その範囲の中間の数字 (2 または 8) を選択します。数値が得られるまで、範囲を半分に分割し続けます。

これは、並べ替えられた配列 (並べ替えられた配列は 1 から 10 までの数字) に対するバイナリ検索です。

コードでそれを実装するには、上記と同じプロセスを続けてください。範囲の中間点を選択し、回答に基づいて新しい範囲を作成します。

これを再帰的に行うJavaのソリューションの1つを次に示します。

public class BinarySearchRecursive
{
    public static final int NOT_FOUND = -1;

    /**
     * Performs the standard binary search
     * using two comparisons per level.
     * This is a driver that calls the recursive method.
     * @return index where item is found or NOT_FOUND if not found.
     */
    public static int binarySearch( Comparable [ ] a, Comparable x )
    {
        return binarySearch( a, x, 0, a.length -1 );
    }

    /**
     * Hidden recursive routine.
     */
    private static int binarySearch( Comparable [ ] a, Comparable x,
                                     int low, int high )
    {
        if( low > high )
            return NOT_FOUND;

        int mid = ( low + high ) / 2;

        if( a[ mid ].compareTo( x ) < 0 )
            return binarySearch( a, x, mid + 1, high );
        else if( a[ mid ].compareTo( x ) > 0 )
            return binarySearch( a, x, low, mid - 1 );
        else
            return mid;
    }

    // Test program
    public static void main( String [ ] args )
    {
        int SIZE = 8;
        Comparable [ ] a = new Integer [ SIZE ];


    for( int i = 0; i < SIZE; i++ )
        a[ i ] = new Integer( i * 2 );

    for( int i = 0; i < SIZE * 2; i++ )
        System.out.println( "Found " + i + " at " +
                                 binarySearch( a, new Integer( i ) ) );
    }
}
于 2010-04-15T18:59:45.310 に答える
3

「再帰的バイナリ検索」をグーグルで検索して出来上がり！

編集-ウィキペディアはすべてを知っています（特にcsに関しては）：

[バイナリ検索アルゴリズムの] 最も単純な実装は再帰的であり、比較によって指定された部分範囲を再帰的に検索します。

   BinarySearch(A[0..N-1], value, low, high) {
       if (high < low)
           return -1 // not found
       mid = low + ((high - low) / 2) 
       if (A[mid] > value)
           return BinarySearch(A, value, low, mid-1)
       else if (A[mid] < value)
           return BinarySearch(A, value, mid+1, high)
       else
           return mid // found
   }
于 2010-04-15T18:56:10.760 に答える
-1

std::binary_searchを使用するだけです。関数が実際に your_favorite_compiler で再帰的に実装されていることをチューターに伝えます。

于 2010-04-15T18:54:52.280 に答える