C++ 中的二进制搜索 [已关闭]

Binary search in C++ [closed]

提问人:Craig Campbell 提问时间:9/22/2012 最后编辑:Mooing DuckCraig Campbell 更新时间:9/22/2012 访问量:1655

问:

基本上,我需要了解如何在屏幕上输出值,以实现二进制搜索的成功部分。我试图更改 的初始值,但它要么崩溃,要么保持不变。我逐步浏览了代码,一切似乎都正常工作。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;

}
C++语言

评论

3赞 mah 9/22/2012
如果初始值 的初始值约为要搜索的元素总数,而不是 2,则可能会获得更好的结果。last
9赞 Code-Apprentice 9/22/2012
你的问题是什么?
3赞 Mooing Duck 9/22/2012
@CraigCampbell:您是否在调试器中逐行执行代码并按照步骤进行操作?
1赞 Kevin 9/22/2012
我不知道这是否与您的问题有关,但不应该出现在 for 循环中。它通常意味着只调用一次,然后再也不会调用。srand
2赞 Jerry Coffin 9/22/2012
有没有特别好的理由来编写自己的二进制搜索而不是使用 or ?lower_boundupper_bound

答:

1赞 Jerry Coffin 9/22/2012 #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;
}

最后,你需要代码来生成一个随机数,搜索它,跟踪搜索次数的统计信息,以及有多少次成功,等等。

0赞 mah 9/22/2012 #2

您有几个问题。

首先,正如我所评论的,您没有正确初始化。last

其次,在这种情况下,您没有正确修改。您正在设置,但您需要改为设置else if(target < array[mid])lastlast = mid + 1;last = mid - 1;

接下来,您没有正确退出循环。只有在第一个>最后一个时才退出 while 循环,但你应该退出它一次;也许战略声明会有所帮助。target == array[mid]break;

当我进行这三项更改时,应用程序每次都会运行到完成,但是我要么收到 0 次,要么收到 100 次成功搜索——两者之间没有。

不过,这应该足以让你走得更远。