-4

基本的に、二分探索の成功部分の値を画面に出力する方法を見つける必要があります。の初期値を変更しようとしましたlastが、クラッシュするか、同じままです。コードをステップ実行したところ、すべてが正しく機能しているようです。

コンパイラからのプログラム サンプル

#include<iostream>

using namespace std;

void binarySearch();

int main()
{
    //Called the function in main
    binarySearch();
    system("pause");
    return 0;
};

//void function for binary Search
void binarySearch()
{
      //creating array
      int array[100];
       array[0] = 1;
       int i,target;
      // using Boolean to create pattern for generated numbers in the array
      bool check = false;

      //loop to implement pattern
      for (int x = 1; x < 100; x++)
      {
        if (check == true)
        {
           array[x] = array[x - 1] + 1;
           check = false;
        }
        else
        {   
           array[x] = array[x - 1] + 2; 
           check = true;

        }
       }

     **Code found online and modified to fit**  

  int first,mid,last,completed,successful,tests;
  completed = 0;
  successful = 0;
  tests = 0;
  double percentage;
  percentage = 1;

  for(int x=0;x<100;x++)
  {
    // Initialize first and last variables.
    first = 0;
    last = 2;
    srand( (unsigned)time( NULL ) );      
    int target = (rand() % 150) + 1;

    while(first <= last)
    {
       mid = (first + last)/2;

       if(target > array[mid])
       {
          first = mid + 1;
          tests++;          
       }
       else if(target < array[mid])
       {
          last = mid + 1;
          tests++;
       }
       else
       {
          first = last - 1;
       }
       if(target == array[mid])
       {
          successful++;
       }
    }
    completed++;
  } 

**Area which the error occur No value for successful**
//Output on screen
cout << endl;
cout << "There were "<< completed <<" searches completed."<< endl; 
cout << "There were "<< successful <<" successful searches." << endl; 
cout << percentage <<"%"<<" of the searches were successful." << endl; 
cout << "There was an average of " << completed << " tests per search." << endl;
cout << endl;

}
4

2 に答える 2

1

コードを多少小さな断片に分割することから始めたいと思います。それぞれの断片は、少なくとも理解できると期待できます。私は、あなたのbinarySearch.

それはこのように見えます：

  int array[100];
   array[0] = 1;
   int i,target;
  // using Boolean to create pattern for generated numbers in the array
  bool check = false;

  //loop to implement pattern
  for (int x = 1; x < 100; x++)
  {
    if (check == true)
    {
       array[x] = array[x - 1] + 1;
       check = false;
    }
    else
    {   
       array[x] = array[x - 1] + 2; 
       check = true;

    }
   }

配列を初期化することになっているので、別の関数に入れてから少し単純化します。最初に関数に：

int init(int array[100]) {
   array[0] = 1;
   int i,target;
  // using Boolean to create pattern for generated numbers in the array
  bool check = false;

  //loop to implement pattern
  for (int x = 1; x < 100; x++)
  {
    if (check == true)
    {
       array[x] = array[x - 1] + 1;
       check = false;
    }
    else
    {   
       array[x] = array[x - 1] + 2; 
       check = true;

    }
   }
}

次に簡略化します：

int init(int *array) { 
    array[0] = 1;

    for (int i=1; i<100; i++)
        array[i] = array[i-1] + 1 + (i&1);
}

次に、次のバイナリ検索部分でほぼ同じことを行いますbinarySearch。

while(first <= last)
{
   mid = (first + last)/2;

   if(target > array[mid])
   {
      first = mid + 1;
      tests++;          
   }
   else if(target < array[mid])
   {
      last = mid + 1;
      tests++;
   }
   else
   {
      first = last - 1;
   }
   if(target == array[mid])
   {
      successful++;
   }

と簡略化:

int *binary_search(int const *left, int const *right, int *tests, int val) { 
    int const *mid = left + (right - left)/2;

    while (left < right) {
        ++*tests;
        if (val < *mid)
            right = mid;
        else
            left = mid + 1;
    }
    return left;
}

最後に、乱数を生成して検索し、検索数と成功数に関する統計を追跡するためのコードが必要になります。

于 2012-09-21T20:13:16.310 に答える
0

いくつかの問題があります。

まず、コメントしたように、last正しく初期化していません。

第二に、このelse if(target < array[mid])場合、last正しく変更していません。設定しlast = mid + 1;ていますが、代わりに設定する必要がありますlast = mid - 1;

次に、ループを正しく終了していません。first > last の場合のみ while ループを終了しますが、代わりに一度終了する必要がありますtarget == array[mid]。おそらく戦略的break;声明が役立つでしょう。

これら 3 つの変更を行うと、アプリケーションは毎回完了するまで実行されますが、検索の成功は 0 回または 100 回のいずれかであり、その間には何もありません。

ただし、これでさらに先に進むことができます。

于 2012-09-21T20:13:22.137 に答える