1

上部にリストされているbinary_search関数に問題があります。どこに行けばいいのかわからない。私は二分探索にあまり精通していません。

#include <iostream>
#include <cstdlib>
#include <fstream>

using namespace std;

void get_input(ifstream& fin, int a[], int size, int & array_size);

void binary_search (int a[], int & array_size)
{
    cout << "Please enter the element you would like to search for \n";
    int element;
    cin >> element;

    int lastindex=array_size-1, startindex=0;

    while (startindex <= lastindex)
    {
        int midindex=(array_size/2);
        if(element > a[midindex])
        {
            startindex=midindex;
        }
        else if (element < a[midindex])
        {
            lastindex=midindex-1;
        }

    }

}

int main()
{
    int array_size=-1;
    int a[100];

    ifstream fin;

    get_input (fin, a, 100, array_size);

    binary_search (a, array_size);

    return 0;
}

void get_input (ifstream& fin, int a[], int size, int & array_size)
{
    fin.open("numbers.txt");
    if (fin.fail())
    {
        cout << "File failed to open";
        exit(1);
    }


    for(int i = 0; i < size; i++)
    {
        a[i] = 0;
    }

    cout << "The numbers in the array are: \n\n";

    for (int i = 0; i < size; i++)
    {
        if (!fin.eof())
        {
            fin >> a[i];
            array_size ++;
        }
    }

    for (int i = 0; i < array_size; i++)
    {
            cout << a[i] << "  ";
    }

    cout << "\n\n\n";
    cout << "The numbers in the array sorted are: \n\n";

   for(int i = 0; i < array_size; ++i )
   {
        int temp2 = a[i];

        for (int j = i+1; j < array_size; ++j )
        {

            if( a[j] < temp2)
            {
                temp2 = a[j];

                int temp = a[i];
                a[i]    = a[j];
                a[j]    = temp;
            }
        }
    }





    for (int i = 0; i < array_size; i++)
    {
            cout << a[i] << "  ";
    }

    cout << "\n\n\n";

    fin.close();
}

完了すると、プログラムはファイルから入力を取得し、それを配列に割り当ててから配列をソートすることを想定しています。この後、バイナリ検索を使用して、ユーザーから指定された番号を見つけ、配列内のその場所をユーザーに表示する必要があります。

更新：見つかったインデックスに対して間違った出力を取得しています.... midindexに1つ追加する必要がありますか？

void binary_search (int a[], int & array_size)
{
    cout << "Please enter the element you would like to search for \n";
    int element;
    cin >> element;

    int lastindex=array_size-1, startindex=0;

    while (startindex <= lastindex)
    {
        int midindex= startindex + (lastindex - startindex) / 2;

        if(element > a[midindex])
        {
            startindex=midindex+1;
        }
        else if (element < a[midindex])
        {
            lastindex=midindex-1;
        }
        else if (element == a[midindex])
        {
            cout<<"Element "<<element<<" found at index "<<midindex<<endl;
            return;
        }



    }

}
4

5 に答える 5

2

変更してみてください

startindex=midindex;

に：

startindex=midindex + 1;

と

int midindex=(array_size/2);

に

int midindex= startindex + (lastindex - startindex) / 2

そして最も重要なのは、要素を見つけたときに何もしていないことです。

if(element == a[midindex]) {
  cout<<"Element "<<element<<" found at index "<<midindex<<endl;
  return;
}
于 2010-10-21T03:13:23.950 に答える
2

私の最初の反応はラインを変えることです

int midindex=(array_size/2);

に

int midindex = startindex + (lastindex - startindex) / 2;

また、探している要素が見つかったかどうかを報告しませんか？要素が見つかった場合を検出するにはif、次のような別のブランチ

if( element == a[midindex] )

挿入できます。それは、ループの外側と結合された、return element;またはその内側を持つことができます。return midindexreturn failure;

編集：私は二分探索のバージョンを書くために何気なく試みました。二分探索は不正確になることで（悪名高い）有名なので、私はそれが正しいとは主張しません。テストケースと出力を含む一部のコードは、コードパッドにアップロードされます。

スニペット：

int *
mybsearch( int const *  const a, size_t const n, int const key ) {

    int * lo = const_cast< int * >( a );
    int * hi = lo + n;

    while( lo <= hi ) {

        int * const mid = lo + (hi - lo) / 2;
        int const midelem = *mid;

        if( key == midelem ) {
            return mid;
        }
        else if( key < midelem ) {
            hi = mid - 1;
        }
        else {
            lo = mid + 1;
        }
    }

    return NULL;
}

メインコードとテストコード：

int main() {

    int const arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
    size_t const num = sizeof( arr ) / sizeof( int );

    int * pos20 = mybsearch( arr, num, 20 );
    assert( pos20 && (*pos20 == 20) );

    int * pos25 = mybsearch( arr, num, 25 );
    assert( !pos25 );

    int * pos5 = mybsearch( arr, num, 5 );
    assert( !pos5 );

    int * pos105 = mybsearch( arr, num, 105 );
    assert( !pos105 );
}
于 2010-10-21T03:15:30.527 に答える
1

二分探索は再帰的アルゴリズムとしてうまく機能します。配列と長さを渡し、中央の値を確認し、必要に応じて配列の上半分/下半分を繰り返します。

于 2010-10-21T03:17:46.543 に答える
0

array_size = 1の場合、正しくないことを慎重に検討してくださいint midindex=(array_size/2);。次に、array_size = 3に一般化します。次に、任意の奇数に一般化します。これには、頭の中または紙の上での小さな実行シミュレーションが必要になります。

于 2010-10-21T03:19:23.013 に答える
0

あなたは近くにいます。あなたはこのようなことをしたいです：

int binary_search ...

要素のインデックスを返すことができるように

while (startindex < lastindex)    
{
    int midindex=(startindex+endindex)/2;
    if(element = a[midindex]) {
        return midindex;
    }
    else if(element > a[midindex])
    {
        startindex=midindex+1;
于 2010-10-21T03:21:39.050 に答える